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 v+f−e=2v + f - e = 2 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 v+f−e=2v + f - e = 2 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 AA, BB, CC and DD, so they are the same graph, K4K_4. The redrawing on the right shows that K4K_4 is planar.

A graph has been drawn with two of its edges crossing. What can you conclude?

Choose one answer

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. F4F_4, the outside face, is the one most often forgotten.

For this graph, v=5v = 5, e=7e = 7 and f=4f = 4, so v+f−e=5+4−7=2v + f - e = 5 + 4 - 7 = 2. Draw any connected planar graph, count, and you will get 2 every time.

Key idea

Euler's formula

For every connected planar graph,

v+f−e=2v + f - e = 2

where vv is the number of vertices, ff the number of faces (including the outside face) and ee 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, v=1v = 1, f=1f = 1 (just the outside) and e=0e = 0, so v+f−e=2v + f - e = 2. Each new edge does one of two things:

  • it reaches out to a new vertex, so vv and ee each go up by 1 and v+f−ev + f - e does not change; or
  • it joins two vertices already in the graph, splitting a face in two, so ff and ee each go up by 1 and again v+f−ev + f - e does not change.

So v+f−ev + f - e stays at 2 however the graph is built.

Worked example

Counting faces and verifying Euler's formula

  • Simple familiar

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.

4 steps

Try it yourself first, then check the working one step at a time.

Method

  1. Count the vertices and edges, and check with the degree total.

  2. Count the faces of a drawing with no crossings, including the outside face.

  3. Substitute into v+f−e=2v + f - e = 2.

Watch out for

  • Forgetting the outside face gives f=4f = 4 and 6+4−9=16 + 4 - 9 = 1.

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

  • Complex unfamiliar

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?

6 steps

Try it yourself first, then check the working one step at a time.

Method

  1. Translate the context into vv, ff and ee, remembering the outside face.

  2. Use the degree total, 2e2e, to link ee to vv.

  3. Substitute into Euler's formula and solve.

Watch out for

  • Using f=7f = 7 gives v=10v = 10 and e=15e = 15. 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 v+f−e=1v + f - e = 1 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 K3,3K_{3,3}, is not planar. Neither is K5K_5.

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 e≤3v−6e \le 3v - 6. For K5K_5, e=10e = 10 but 3v−6=93v - 6 = 9, so K5K_5 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 vv, ff and ee before you substitute: "v=6v = 6, e=9e = 9, so 6+f−9=26 + f - 9 = 2 and f=5f = 5." 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 v+f−e=2v + f - e = 2 links the vertices, faces and edges.

  • Combine it with the sum of the degrees, 2e2e, when a problem gives degrees instead of edges.

  • In context, translate carefully: enclosed regions + 1 outside region = ff.

Finished the lesson?

Try the 4 quick checks above and the lesson completes itself, or mark it complete now.

Lesson 4 of 80% read

Save your progress with a free account