Year 11 Maths - Specialist (Unit 1 and Unit 2) Graph theory

Planar graphs and Euler's formula

Q: What is Euler's formula for planar graphs?

For a connected planar graph, v plus f minus e equals 2, where v is the number of vertices, e is the number of edges and f is the number of faces, counting the outer unbounded face.

Q: How do I find the number of vertices, edges or faces?

Rearrange v plus f minus e equals 2 for the unknown: f equals 2 minus v plus e, or v equals 2 minus f plus e, or e equals v plus f minus 2. Substitute the two known counts and simplify.

Q: How many edges does a complete graph have?

The complete graph K-n joins every pair of vertices, so it has n times n minus 1, all over 2, edges. A regular graph with n vertices each of degree r has n times r over 2 edges.

Q: Which complete and bipartite graphs are planar?

Every tree is planar. The complete graph K-n is planar exactly when n is at most 4, and the complete bipartite graph K-m-n is planar exactly when m is at most 2 or n is at most 2. So K-5 and K-3-3 are the smallest non-planar graphs.

20 practice questions 0 video lessons Theory + worked examples

Master planar graphs and Euler's formula in Year 11 VCE Specialist Mathematics. A planar graph can be drawn with no edges crossing, and for any connected planar graph Euler's formula $v+f-e=2$ links the vertices, edges and faces. It sits in the Algebra, number and structure area of study of the VCE Mathematics Study Design (VCAA), within the Graph theory topic of Unit 1.

You will learn to count faces (including the outer face), rearrange Euler's formula to find any of $v$, $e$ or $f$, and decide when trees, the complete graph $K_n$ and the complete bipartite graph $K_{m,n}$ are planar.

Practice 20 questions

Practice questions

Every question with a fully worked solution.

Start practising

Theory

Planar graphs are graphs that can be drawn in the plane so that no two edges cross. For any connected planar graph, Euler's formula $v+f-e=2$ ties together the numbers of vertices $v$, edges $e$ and faces $f$. In Year 11 Specialist Mathematics you rearrange it to find any one of $v$, $e$ or $f$, count edges with $\dfrac{n(n-1)}{2}$ for the complete graph $K_n$ and $\dfrac{nr}{2}$ for a regular graph, and decide when a graph is planar.

A graph is planar if it can be drawn in the plane so that no two edges cross. The same graph can often be drawn with crossings in one picture and without crossings in another — what matters is whether some crossing-free drawing exists.

Such a drawing divides the plane into regions called faces. The faces include the outer unbounded region, so a triangle drawn in the plane has two faces: the inside and the outside.

A graph is connected if you can travel between any two vertices along edges. For a connected planar graph, Euler's formula relates the three counts:

Euler's formula: for a connected planar graph, \(v+f-e=2\), where \(v\) is the number of vertices, \(e\) the number of edges and \(f\) the number of faces (including the outer face).

The degree of a vertex is the number of edges meeting it. The handshaking lemma says the degrees add up to twice the number of edges, $\sum \deg = 2e$, because every edge has two ends. A regular graph is one in which every vertex has the same degree.

The complete graph $K_n$ joins every pair of its $n$ vertices; a tree is a connected graph with no cycles; and the complete bipartite graph $K_{m,n}$ joins each of $m$ vertices to each of $n$ others. These families have neat planarity rules, covered in the Formulas tab.

A square with one diagonal: $v=4$, $e=5$. The diagonal makes two triangular faces $f_1,f_2$; with the outer face $f_3$ that is $f=3$, and $4+3-5=2$ as Euler's formula predicts.

The complete graph $K_4$ drawn without crossings as a triangle plus a centre vertex: $v=4$, $e=6$, $f=4$ (three inner faces and the outer face), so $K_4$ is planar and $4+4-6=2$.

Euler's formula for a connected planar graph links the three counts; rearrange it to isolate whichever one is unknown:

\[ v+f-e=2 \]

v + f - e = 2

\[ f=2-v+e,\qquad v=2-f+e,\qquad e=v+f-2 \]

The handshaking lemma gives the total degree from the number of edges (each edge has two ends):

\[ \sum \deg = 2e \]

\sum \deg = 2 e

The complete graph $K_n$ joins every pair of vertices, and a regular graph has every vertex of the same degree $r$:

\[ K_n:\ e=\dfrac{n(n-1)}{2}, \qquad \text{$r$-regular on $n$ vertices}:\ e=\dfrac{nr}{2} \]

e = \frac{n (n - 1)}{2}

A tree on $n$ vertices has $e=n-1$ edges.

Planarity rules. Every tree is planar. The complete graph \(K_n\) is planar exactly when \(n\le 4\) (so \(K_5\) is not planar). The complete bipartite graph \(K_{m,n}\) is planar exactly when \(m\le 2\) or \(n\le 2\) (so \(K_{3,3}\) is not planar).

Using Euler's formula and the counting rules

Check the graph is connected and planar — Euler's formula $v+f-e=2$ applies to a connected planar graph. Remember the outer region counts as a face.
List what you know. Write down which of $v$, $e$, $f$ are given.
Rearrange for the unknown: $f=2-v+e$, or $v=2-f+e$, or $e=v+f-2$. Substitute and simplify one step at a time.
Counting edges: for a complete graph use $e=\dfrac{n(n-1)}{2}$; for a regular graph use $e=\dfrac{nr}{2}$ (or the handshaking lemma $\sum\deg=2e$); for a tree use $e=n-1$.
Deciding planarity: a tree is always planar; $K_n$ is planar iff $n\le 4$; $K_{m,n}$ is planar iff $m\le 2$ or $n\le 2$.

The prism below shows every count at once: $v=6$, $e=9$, and Euler's formula gives $f=2-6+9=5$ faces.

Example 1 — Faces from Euler's formula

A connected planar graph has $6$ vertices and $9$ edges. Use Euler's formula $v+f-e=2$ to find the number of faces $f$.

Solution

Rearrange Euler's formula to make $f$ the subject:

$v+f-e$	$=$	$2$
$f$	$=$	$2-v+e$

Substitute $v=6$ and $e=9$:

$f$	$=$	$2-6+9$
	$=$	$5$

The graph has $f = 5$ faces.

Example 2 — Edges from Euler's formula

A connected planar graph has $7$ vertices and $5$ faces. Use Euler's formula to find the number of edges $e$.

Solution

Rearrange Euler's formula to make $e$ the subject:

$v+f-e$	$=$	$2$
$e$	$=$	$v+f-2$

Substitute $v=7$ and $f=5$:

$e$	$=$	$7+5-2$
	$=$	$10$

The graph has $e = 10$ edges.

Example 3 — Edges of a complete graph, and planarity

How many edges does the complete graph $K_6$ have, and is $K_6$ planar? (Recall $K_n$ has $\dfrac{n(n-1)}{2}$ edges and is planar exactly when $n\le 4$.)

Solution

Substitute $n=6$ into $\dfrac{n(n-1)}{2}$:

$\dfrac{n(n-1)}{2}$	$=$	$\dfrac{6\times 5}{2}$
	$=$	$\dfrac{30}{2}$
	$=$	$15$

Test planarity against $n\le 4$:

$n$	$=$	$6 > 4$
	$\Rightarrow$	$\text{not planar}$

$K_6$ has $15$ edges and is not planar (since $6>4$).

Example 4 — Edges of a regular graph

A graph has $10$ vertices, each of degree $3$ (it is $3$-regular). How many edges does it have? (A regular graph with $n$ vertices each of degree $r$ has $\dfrac{nr}{2}$ edges.)

Solution

Substitute $n=10$ and $r=3$ into $\dfrac{nr}{2}$:

$\dfrac{nr}{2}$	$=$	$\dfrac{10\times 3}{2}$
	$=$	$\dfrac{30}{2}$
	$=$	$15$

Check with the handshaking lemma $\sum\deg=2e$:

$\sum\deg$	$=$	$10\times 3 = 30$
$2e$	$=$	$30$
$e$	$=$	$15\ \checkmark$

The graph has $e = 15$ edges.

Example 5 — Reading a graph and finding its faces

The triangular-prism graph shown has $6$ vertices and $9$ edges. How many faces does it have, including the outer face?

Solution

Read $v$ and $e$ from the drawing:

$v$	$=$	$6$
$e$	$=$	$9$

Apply Euler's formula $f=2-v+e$:

$f$	$=$	$2-6+9$
	$=$	$5$

The prism has $f = 5$ faces: the inner triangle, three four-sided faces, and the outer face.

Common pitfalls

Forgetting the outer face. Faces include the unbounded region outside the graph. A single triangle has $2$ faces, not $1$.

Mis-rearranging Euler's formula. From $v+f-e=2$: to find $f$ use $f=2-v+e$; to find $v$ use $v=2-f+e$; to find $e$ use $e=v+f-2$. Move terms carefully — a sign slip changes the answer.

Confusing "crossings in one drawing" with "not planar". A graph is planar if any drawing avoids crossings. $K_4$ looks like it has a crossing when drawn as a square with both diagonals, but it can be redrawn with none, so it is planar.

Mixing up the edge formulas. Use $\dfrac{n(n-1)}{2}$ only for a complete graph $K_n$; use $\dfrac{nr}{2}$ for a regular graph of degree $r$. They agree only when $r=n-1$.

Guessing planarity. Learn the rules: every tree is planar, $K_n$ is planar iff $n\le 4$, and $K_{m,n}$ is planar iff $m\le 2$ or $n\le 2$. So $K_5$ and $K_{3,3}$ are the smallest non-planar cases.

Frequently asked questions

What is a planar graph?

A planar graph is one that can be drawn in the plane so that no two edges cross. The graph is planar as long as some crossing-free drawing exists, even if other drawings have crossings.

What is Euler's formula for planar graphs?

For a connected planar graph, $v+f-e=2$, where $v$ is the number of vertices, $e$ the number of edges and $f$ the number of faces, counting the outer unbounded face.

How do I find the number of vertices, edges or faces?

Rearrange $v+f-e=2$ for the unknown: $f=2-v+e$, $v=2-f+e$, or $e=v+f-2$. Substitute the two known counts and simplify.

What counts as a face of a planar graph?

A face is a region the drawing splits the plane into, including the outer unbounded region. For example, a triangle drawn in the plane has two faces: the inside and the outside.

How many edges does a complete graph have?

The complete graph $K_n$ joins every pair of vertices, so it has $\dfrac{n(n-1)}{2}$ edges. A regular graph with $n$ vertices each of degree $r$ has $\dfrac{nr}{2}$ edges.

Which complete and bipartite graphs are planar?

Every tree is planar. The complete graph $K_n$ is planar exactly when $n\le 4$, and the complete bipartite graph $K_{m,n}$ is planar exactly when $m\le 2$ or $n\le 2$. So $K_5$ and $K_{3,3}$ are the smallest non-planar graphs.

← Previous subtopic

Bipartite graphs, trees and regular graphs

Next subtopic →

Trails, circuits, Euler and Hamiltonian paths

\(v+f-e\)	\(=\)	\(2\)
\(f\)	\(=\)	\(2-v+e\)

\(f\)	\(=\)	\(2-6+9\)
	\(=\)	\(5\)

\(v+f-e\)	\(=\)	\(2\)
\(e\)	\(=\)	\(v+f-2\)

\(e\)	\(=\)	\(7+5-2\)
	\(=\)	\(10\)

\(\dfrac{n(n-1)}{2}\)	\(=\)	\(\dfrac{6\times 5}{2}\)
	\(=\)	\(\dfrac{30}{2}\)
	\(=\)	\(15\)

\(\dfrac{nr}{2}\)	\(=\)	\(\dfrac{10\times 3}{2}\)
	\(=\)	\(\dfrac{30}{2}\)
	\(=\)	\(15\)

\(\sum\deg\)	\(=\)	\(10\times 3 = 30\)
\(2e\)	\(=\)	\(30\)
\(e\)	\(=\)	\(15\ \checkmark\)

\(n\)	\(=\)	\(6 > 4\)
	\(\Rightarrow\)	\(\text{not planar}\)

Planar graphs and Euler's formula

📖 Theory

Using Euler's formula and the counting rules

Common pitfalls

Frequently asked questions

Theory