Lesson 4: Planar graphs and Euler's formula

Planning garden paths with Euler's formula

SkillsEuler's formulaDegrees of vertices

Worked example

  • 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?

1 of 6 steps
  1. 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 v+f−e=2v + f - e = 2.

Try a similar one

A fresh question of the same kind, checked as you answer, with hints and a full solution.

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.

Save your progress with a free account