Planning a Snowplow Route

A snowplow must drive every street in a neighborhood and return to the depot. If every intersection meets an even number of streets, one loop covers each street exactly once. Every odd intersection forces some streets to be driven twice, and pairing the odd ones up cheaply is the whole planning problem.

How it works

Euler circuits and odd-degree vertices

In one sentence

A connected graph has an Euler circuit if and only if every vertex has even degree. The Chinese postman problem asks for the shortest closed walk that covers every edge; its extra length is the weight of a minimum-weight perfect matching of the odd-degree vertices, which can be found in polynomial time.

General formula

\text{one loop covers every street once} \iff {\htmlData{sym=0}{\deg(v)}} \text{ is even at every intersection } v

Every visit to an intersection pairs an arriving street with a departing one. An odd intersection leaves a street unpaired, and some repeated trip has to fix it.

What the symbols mean

$\deg(v)$
Degree
How many streets meet at intersection v.

Treat intersections as vertices and streets as edges. A route that drives every street exactly once and returns home is an Euler circuit.
Each pass through an intersection uses one street in and one out, so an Euler circuit needs every degree to be even (and the streets to be connected).
Odd intersections come in pairs (the handshake lemma). Each pair must be joined by streets driven twice, so the planner pairs them as cheaply as possible: the Chinese postman problem.
Closing streets changes degrees, and the right closures, or one-way rules, can make every degree even.

Learn the math

Euler and Hamilton PathsDiscrete · Lesson 39, Graph Theory

Planning a Snowplow Route