Lesson 7: Eulerian trails and circuits

Planning a street sweeper's route

SkillsEulerian trails and circuitsShortest paths by trial and error

Worked example

  • Complex unfamiliar

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.

1 of 6 steps
  1. 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.

Try a similar one

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

Method

  1. Find the vertices of odd degree.

  2. With two odd vertices, repeat the shortest path between them.

  3. Total distance = all the edges + the repeated path.

Watch out for

  • Repeating BEBE and EFEF (650 m) gives a valid route, but not the shortest.

  • Answering 3050 m, which ignores the doubling back.

Save your progress with a free account