Euler's formula for planar graphs
Studying this course? Keep your progress in one place.
Key facts
- A planar graph can be drawn with no edges crossing; the drawing splits the plane into faces.
- The outer face always counts as a face.
- For a connected planar graph, .
- A new vertex joined by one edge leaves unchanged; an edge between existing vertices adds one face.
- The sum of the face degrees is , and in a simple graph every face has degree at least .
Planar graphs and faces
A planar graph can be drawn with no crossings, and the regions this creates, including the outside, are its faces.
A planar drawing divides the plane into regions called faces. The unbounded region outside the graph is the outer face, and it always counts.
Count faces from a drawing without crossings. A tree (connected, no cycles) has and just one face, the outer face, because it encloses nothing.
A cube drawn flat has 8 vertices and 12 edges. How many faces does it have, counting the outer face?
Euler's formula
For any connected planar graph, vertices minus edges plus faces always equals .
For a connected planar graph with vertices, edges and faces (including the outer face), Euler's formula holds.
Given any two of , , you can find the third. Rearranged: and .
- Euler's formula
Worked example
A connected planar graph has vertices and edges. Find the number of faces.
- 1
Write down Euler's formula: .
- 2
Substitute: .
- 3
Solve: .
A connected planar graph has and . How many vertices does it have?
Building up a graph
Only an edge between two existing vertices adds a face; a pendant vertex or a subdivision does not.
Euler's formula shows how changes affect the number of faces.
- Adding a new vertex joined by one edge (a pendant vertex) changes and by each, so is unchanged.
- Adding an edge between two existing vertices, without crossings, splits a face in two, so increases by .
- Subdividing an edge adds one vertex and one edge, so is unchanged.
| Pendant vertex | Edge between existing vertices | Subdivision | |
|---|---|---|---|
| Change in | +1 | 0 | +1 |
| Change in | +1 | +1 | +1 |
| Change in | 0 | +1 | 0 |
Pendant vertex
- Change in :
- +1
- Change in :
- +1
- Change in :
- 0
Edge between existing vertices
- Change in :
- 0
- Change in :
- +1
- Change in :
- +1
Subdivision
- Change in :
- +1
- Change in :
- +1
- Change in :
- 0
Worked example
A planar graph has , , . Two pendant vertices and one further edge are added. Find the new number of faces.
- 1
Two pendant vertices add vertices and edges: , .
- 2
One further edge makes .
- 3
Use Euler's formula: , so .
An edge is added between two existing vertices of a planar graph without crossings. What happens to ?
Counting around faces
Each edge borders faces on two sides, so the face degrees add up to twice the number of edges.
The degree of a face is the number of edges around its boundary. Each edge has two sides, and each side lies in a face.
If all faces have degree , then . With : , so and .
In a simple graph every face has degree at least , so . With , we get and , so no such planar graph exists.
- Sum of face degrees
- Simple planar graph
A connected simple planar graph has and every face has degree . How many edges does it have?
Try an exam question
A connected simple planar graph has vertices and every face has degree . Find the number of edges and the number of faces.
[4 marks]
- [1]The sum of the face degrees is , so .
- [1]Euler's formula: .
- [1] gives .
- [1].
That's the notes covered.
Carry on to the next subtopic.
Try a question
How many faces does have, including the outer face?
1 mark, marked against the mark scheme
How many faces does have, including the outer face?
1 mark, marked against the mark scheme