Suppose a street sweeper must clean every road in a neighborhood and return to its depot. It sounds reasonable to plan a route that uses each road exactly once. But sometimes no such route exists, however cleverly the driver turns. The obstacle is not traffic or a badly placed depot. It is a small fact about even and odd numbers.
Turn the streets into a drawing
Imagine drawing a dot at every intersection and a line along every road between intersections. Mathematicians call the dots vertices and the lines edges. The length of each edge can stand for the distance the sweeper must drive along that road.

Now look at a single intersection on a route that starts and ends at the depot. Each time the sweeper arrives, it must leave. The roads it uses there therefore come in arrival-and-departure pairs. That includes the depot: its first departure pairs with its final arrival. If the sweeper travels every road exactly once, every intersection must have an even number of roads meeting there.
The number of roads meeting at an intersection is its degree. An intersection with three roads has odd degree, so a closed route cannot use each of those three roads just once. One trip would arrive without an unused road to leave by—or leave without a matching arrival.
A neighborhood with one troublesome shortcut
Picture four intersections, A, B, C, and D, at the corners of a square. Each side of the square is a 2-kilometer road. A diagonal road runs from A to C and measures 5 kilometers. The sweeper must clean all five roads, and its depot is at A.
The total road length is 2 + 2 + 2 + 2 + 5 = 13 kilometers. That is the absolute minimum the sweeper could drive if it did not need to return. Indeed, it could take A–B–C–D–A–C, cleaning every road once and finishing at C.
But A and C each have three roads meeting there. B and D each have two. A route that returns to A cannot cover all 13 kilometers exactly once: the odd intersections prevent it. Some roads must be repeated.
Which roads should be repeated?
Repeating a road adds another use of that road at both of its endpoints. To make the degrees at A and C even, we need to add a path connecting them. We could repeat the 5-kilometer diagonal. But the path through B is shorter: A–B–C is just 2 + 2 = 4 kilometers.
So the shortest possible closed trip is at least 13 + 4 = 17 kilometers. We can reach that total with the route A–B–C–D–A–C–B–A. It cleans every road, repeats only A–B and B–C, and ends at the depot. Because it reaches the lower bound, we know no shorter closed trip exists.
Notice the subtlety: the sweeper still has to clean the long diagonal. It simply should not choose that diagonal as the extra road to drive. The cheapest way to fix the route is to repeat the shorter path, not necessarily the road that seems most troublesome.
When there are more odd intersections
A street network can have four, six, or more odd-degree intersections—but never an odd number of them. Each road contributes one to the degree at each end, so adding up all degrees counts every road twice. An even total cannot contain an odd number of odd contributions.
To plan a closed route, pair up the odd intersections and add repeat trips connecting each pair. With several pairs, the nearest-looking match for one intersection may force an expensive match elsewhere. The task is to find the pairing with the smallest total extra distance. This is the heart of the route inspection problem, also known as the Chinese postman problem.
Real street sweepers face more constraints than our drawing captures: one-way roads, roads that need cleaning on both sides, and traffic rules all matter. But the parity check remains a powerful first question. Before searching for a clever route, count the roads at each intersection. Odd-degree intersections tell you where an exactly-once closed trip is impossible—and where the unavoidable extra driving begins.


Leave a Reply
You must be logged in to post a comment.