Lesson 4: Planar graphs and Euler's formula
Planning garden paths with Euler's formula
SkillsEuler's formulaDegrees of vertices
Worked example
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 ✓
Answer
The plan has 12 junctions and 18 paths.
Try a similar one
A fresh question of the same kind, checked as you answer, with hints and a full solution.
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.