Lesson 7: Eulerian trails and circuits
Planning a street sweeper's route
SkillsEulerian trails and circuitsShortest paths by trial and error
Worked example
A council street sweeper must travel along every street shown at least once, starting and finishing at the depot. Street lengths are in metres.
(a) Explain why the sweeper cannot travel every street exactly once and return to the depot.
(b) Find the shortest total distance the sweeper must travel, and state which streets it should travel twice.
Step 1: Recognise what is being asked
Travelling every street exactly once and returning to the start is an Eulerian circuit. That needs a connected graph in which every vertex has even degree.
Step 2: Check the degrees
Depot 2, 4, 3, 2, 4, 3. Vertices and have odd degree, so there is no Eulerian circuit: the sweeper must travel some streets twice.
Step 3: Decide which streets to repeat
Repeating the streets along a route from to adds 1 to the degrees of and , making them even, and 2 to each vertex in between, keeping them even. So the sweeper should repeat the shortest path from to .
A route passing through a vertex arrives on one edge and leaves on another, adding 2 there. Only the two ends of the repeated route change from odd to even.
Step 4: Find the shortest path from B to F
- ––: m
- ––: m
- Longer routes, such as ––– at 950 m, are not needed.
The shortest is ––, 600 m.
Step 5: Total the distance
All the streets: m. Adding the repeated 600 m gives m.
Step 6: Give a route that achieves it
For example: Depot–––––––––––Depot. It uses and twice and every other street once, a total of 3650 m. ✓
Answer
(a) and have odd degree, so the network has no Eulerian circuit. (b) 3650 m, travelling streets and twice — the shortest path from to .
Try a similar one
A fresh question of the same kind, checked as you answer, with hints and a full solution.
Method
Find the vertices of odd degree.
With two odd vertices, repeat the shortest path between them.
Total distance = all the edges + the repeated path.
Watch out for
Repeating and (650 m) gives a valid route, but not the shortest.
Answering 3050 m, which ignores the doubling back.