Euler's formula for planar graphs

Euler's formula for planar graphs

Spec DA3 · AQA A-Level Further Maths: Revision notes

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, v−e+f=2v-e+f=2.
  • A new vertex joined by one edge leaves ff unchanged; an edge between existing vertices adds one face.
  • The sum of the face degrees is 2e2e, and in a simple graph every face has degree at least 33.

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 e=v−1e=v-1 and just one face, the outer face, because it encloses nothing.

ABCDEFGH
A cube drawn flat: 1 inner face, 4 side faces and the outer face make 6 faces.

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 22.

For a connected planar graph with vv vertices, ee edges and ff faces (including the outer face), Euler's formula holds.

Given any two of vv, ee, ff you can find the third. Rearranged: e=v+f−2e=v+f-2 and v=2+e−fv=2+e-f.

  • Euler's formulav−e+f=2v-e+f=2

Worked example

A connected planar graph has 88 vertices and 1212 edges. Find the number of faces.

A connected planar graph has e=15e=15 and f=8f=8. 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 vv and ee by 11 each, so ff is unchanged.
  • Adding an edge between two existing vertices, without crossings, splits a face in two, so ff increases by 11.
  • Subdividing an edge adds one vertex and one edge, so ff is unchanged.

Pendant vertex

Change in vv:
+1
Change in ee:
+1
Change in ff:
0

Edge between existing vertices

Change in vv:
0
Change in ee:
+1
Change in ff:
+1

Subdivision

Change in vv:
+1
Change in ee:
+1
Change in ff:
0

Worked example

A planar graph has v=9v=9, e=15e=15, f=8f=8. Two pendant vertices and one further edge are added. Find the new number of faces.

An edge is added between two existing vertices of a planar graph without crossings. What happens to ff?

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 ff faces have degree 33, then 3f=2e3f=2e. With v=7v=7: 7−e+2e3=27-e+\frac{2e}{3}=2, so e=15e=15 and f=10f=10.

In a simple graph every face has degree at least 33, so 2e≥3f2e\ge3f. With v=12v=12, e=31e=31 we get f=21f=21 and 3f=63>62=2e3f=63>62=2e, so no such planar graph exists.

  • Sum of face degrees2e2e
  • Simple planar graph2e≥3f2e\ge3f

A connected simple planar graph has v=6v=6 and every face has degree 33. How many edges does it have?

Try an exam question

A connected simple planar graph has 88 vertices and every face has degree 33. Find the number of edges and the number of faces.

[4 marks]

That's the notes covered.

Carry on to the next subtopic.

Try a question

How many faces does GG have, including the outer face?

1 mark, marked against the mark scheme

Revision notes