Lesson 4 of 8 · 17 min
Planar graphs and Euler's formula
Decide whether a graph is planar by redrawing it without crossings, count its faces, and use Euler's formula to find a missing count or test a claim.
What you will be able to do
- Explain what a planar graph is, and redraw a graph to remove crossings.
- Count the faces of a planar graph, including the outside face.
- Apply Euler's formula to find an unknown number of vertices, faces or edges.
- Use Euler's formula with the sum of the degrees to solve problems in context.
On a printed circuit board, the copper tracks joining the components cannot cross — two tracks touching would short-circuit the board. Plans for water pipes and cables have a similar problem.
So it matters whether a network can be drawn on a flat surface with no edges crossing.
Definition
Planar graph
A planar graph is a graph that can be drawn on a flat surface with no edges crossing. A planar graph may still be drawn with crossings — what matters is whether it can be redrawn without them.
Both drawings join every pair of , , and , so they are the same graph, . The redrawing on the right shows that is planar.
A graph has been drawn with two of its edges crossing. What can you conclude?
Definition
Face
The edges of a planar drawing divide the page into regions called faces. The region outside the graph, which goes on forever, is a face too.
This graph has 4 faces. , the outside face, is the one most often forgotten.
For this graph, , and , so . Draw any connected planar graph, count, and you will get 2 every time.
Key idea
Euler's formula
For every connected planar graph,
where is the number of vertices, the number of faces (including the outside face) and the number of edges. The formula is in the QCAA formula book.
Why Euler's formula works
Build any connected planar graph one edge at a time, starting from a single vertex. At the start, , (just the outside) and , so . Each new edge does one of two things:
- it reaches out to a new vertex, so and each go up by 1 and does not change; or
- it joins two vertices already in the graph, splitting a face in two, so and each go up by 1 and again does not change.
So stays at 2 however the graph is built.
Worked example
Counting faces and verifying Euler's formula
The planar graph shown is drawn with no edges crossing.
(a) State the number of vertices, edges and faces.
(b) Show that Euler's formula holds for the graph.
Step 1: Count the vertices
, so .
Step 2: Count the edges in groups
Outer triangle 3, inner triangle 3, and 3 edges joining them, so .
Counting in groups is safer than counting one by one. Check: every vertex has degree 3, and .
Step 3: Count the faces
Inside the inner triangle: 1. Between the triangles: 3 four-sided regions (, and ). Outside the graph: 1. So .
The region outside the graph is a face. It is the one most often missed.
Step 4: Substitute into Euler's formula
✓
Try it yourself first, then check the working one step at a time.
Answer
(a) , and . (b) , so Euler's formula holds.
Method
Count the vertices and edges, and check with the degree total.
Count the faces of a drawing with no crossings, including the outside face.
Substitute into .
Watch out for
Forgetting the outside face gives and .
A connected planar graph has 8 vertices and 12 edges. How many faces does it have?
A connected planar graph has 7 vertices and 5 faces. How many edges does it have?
Worked example
Planning garden paths with Euler's formula
A landscape designer is planning a community garden. Paths meet at junctions, and the paths divide the garden into 7 enclosed garden beds. No paths cross except at junctions, every junction can be reached from every other, and exactly three paths meet at every junction.
How many junctions and how many paths are in the plan?
Step 1: Match the plan to a graph
Junctions are vertices, paths are edges and regions are faces. The plan is a connected planar graph, so .
Step 2: Count the faces carefully
The 7 enclosed beds are faces, and so is the region outside the plan: .
Euler's formula counts the outside region as a face.
Step 3: Link the edges to the vertices with degrees
Every vertex has degree 3, so the degree total is . It is also , so and .
Step 4: Substitute into Euler's formula and solve
Step 5: Find the number of edges
Step 6: Check both conditions
✓ and ✓
Try it yourself first, then check the working one step at a time.
Answer
The plan has 12 junctions and 18 paths.
Method
Translate the context into , and , remembering the outside face.
Use the degree total, , to link to .
Substitute into Euler's formula and solve.
Watch out for
Using gives and . It satisfies the formula you set up, but that plan has only 6 enclosed beds — the outside region was left out.
A connected planar graph has the same number of faces as vertices, and it has 14 edges. How many vertices does it have?
Common mistake
Where Euler's formula seems to fail
- Forgetting the outside face. You get instead of 2.
- Counting faces in a drawing with crossings. Redraw the graph without crossings first; a crossing does not create a vertex or new faces.
- Using it on a graph that is not connected. The formula is for connected planar graphs.
Extension: graphs that are not planar
Try connecting three houses to water, gas and electricity without any lines crossing. It cannot be done: the graph, written , is not planar. Neither is .
Euler's formula is the key to proving this. In a simple planar graph every face is bordered by at least 3 edges, which leads to . For , but , so cannot be planar. You will not be asked to prove that a graph is non-planar in General Mathematics, but it explains why some real networks need an overpass or a tunnel.
Exam tip
Write , and before you substitute: ", , so and ." If asked to define a planar graph, say that it can be drawn with no edges crossing.
Summary
A planar graph can be drawn with no edges crossing; a drawing with crossings may still be redrawn without them.
The faces of a planar drawing are the regions it makes, including the outside region.
For a connected planar graph, Euler's formula links the vertices, faces and edges.
Combine it with the sum of the degrees, , when a problem gives degrees instead of edges.
In context, translate carefully: enclosed regions + 1 outside region = .
Finished the lesson?
Try the 4 quick checks above and the lesson completes itself, or mark it complete now.