The streets a postman walks twice

A walk that splices in its own detours built a closed walk crossing every edge of a graph exactly once, whenever every vertex has even degree, and noted that any connected graph at all has a closed walk crossing every edge exactly twice. Between those two lies the practical question. A postman has to walk every street of a district and return to the depot. Some streets will have to be walked twice. Which ones, and how few?

The problem was posed and solved in 1960 by the Chinese mathematician Kwan Mei-Ko, working on the routes of postal workers, and it has been called the Chinese postman problem since. The answer has a clean shape: the repeated streets form paths that join the odd-degree corners in pairs, and the best route repeats the cheapest such set of paths.

Why the repeated streets pair up the odd corners #

Take any closed route that walks every street at least once. Record, for each street, how many extra times it is walked beyond the first. The extra walks form a second, smaller network — the repeated streets — and the claim is that in this network the corners of odd degree are exactly the odd corners of the district.

The reason is the counting argument from Seven bridges. The route is closed, so every corner is entered as often as it is left, and the total number of times its streets are walked is even. That total is the corner’s degree in the district plus its degree in the network of repeats. For the sum to be even, the two must have the same parity. So a corner that is odd in the district must be odd in the repeats, and a corner that is even must be even.

Now a network in which exactly the corners $v_1, \dots, v_{2k}$ have odd degree always contains $k$ paths that join those corners in pairs: start at an odd corner and walk along repeated streets without reusing one, and the walk can only stop at another odd corner, by the same argument that told Hierholzer’s walk it could only stall at home. Remove that path and repeat. So every route repeats, at the least, a set of paths pairing up the odd corners, and its extra length is at least the length of the cheapest such pairing.

The bound is also reached. Pick the cheapest pairing, measured by shortest paths between the paired corners, and add a second copy of each street on those paths. Every corner is now even, and the splicing construction produces a round that walks each original street once and each added copy once. The shortest round is the total length of the streets plus the cheapest pairing of the odd corners, and nothing about the problem is harder than finding that pairing.

In the hero figure the eight odd corners are the midpoints of the outer edges, where three streets meet. The cheapest pairing joins them two by two along the outer edge, one block apart, and repeats four blocks. Every other pairing repeats more. The round is 28 blocks, and there is no shorter way to walk all 24.

Twice everything, against the pairing #

The crude answer from the splicing essay was that every connected network can be walked with every street exactly twice. Measured against the exact answer, that crude bound is expensive. The three-by-three grid would take 48 blocks instead of 28. Königsberg would take fourteen crossings instead of nine. The irregular district drawn below would take 48.26 units instead of 29.34. In each case the doubling repeats every street while the pairing repeats only a few — four single blocks of the grid’s 24, two bridges of Königsberg’s seven.

The gap has a clean explanation. Doubling makes every corner even, which is more than is needed: the even corners were already even and did not need touching. The pairing touches only the odd corners, and only along the cheapest paths between them. The extra length a postman pays is set by the odd corners and nothing else, and a district whose corners are nearly all even costs little more than the length of its streets.

That also tells a planner where effort goes. Adding a street between two odd corners makes both even and can shorten the round, even though it adds a street to walk; removing a dead end, whose far corner is odd, removes a forced repetition. The round’s length is a property of the parity pattern, and changing the network changes the pattern.

Königsberg, walked properly #

The city whose bridges started the subject has the smallest interesting instance.

All four landmasses are odd, so there are three ways to pair them. Pairing the north bank with the island and the east landmass with the south bank costs one bridge each, since they are joined directly; so does pairing north with east and island with south. Pairing north with south costs two, since no bridge joins them. The cheapest pairings repeat two bridges, and the shortest round crosses nine.

That is the answer to the citizens’ puzzle in its natural generalisation. They could not cross each bridge exactly once; they could cross all seven by crossing two of them twice, and not by crossing only one twice, because one extra crossing changes the parity of only two landmasses and leaves the other two odd.

An irregular district, and fifteen pairings #

On a real district the streets have different lengths and the shortest paths between odd corners wind through several streets. The pairing then has to be chosen with care, and the number of pairings grows quickly.

With six odd corners there are fifteen pairings: the first corner can be paired with any of five others, the next unpaired corner with any of three, and the last two are forced, so $5 \times 3 \times 1 = 15$. Each pairing is priced by adding the shortest distance between its two corners in each pair, computed through the whole network.

The spread is wide: the worst pairing costs eighty per cent more than the best, and a route built from it would be nearly four units longer. The prices also come in clusters — several pairings tie at 7.18, several at 9.22 — because they share the same long path between one pair and differ only in how the rest are matched. That clustering is what makes the choice interesting: a single good decision about one pair does most of the work, and the rest is tidying up.

Pairing the nearest first is not the answer #

The obvious shortcut is to pair the two closest odd corners, then the two closest of those left, and so on. It is fast and it is wrong.

The closest pair is 2 and 3, one unit apart, and pairing them first looks like a bargain. It leaves 0 and 5, which are five apart, and the total is six. The best pairing ignores the bargain and takes two pairs of distance two each, for four. The greedy choice made a small saving on one pair and forced a large cost on another, and nothing local warns that this will happen.

The number of pairings to try, though, grows too fast for exhaustion to be the method. Eight odd corners have 105 pairings, sixteen have over two million, and forty have more than $10^{23}$. What rescued the problem was Jack Edmonds’s algorithm of 1965 for finding the cheapest pairing — a minimum-weight perfect matching — in a number of steps polynomial in the number of corners. Its difficulty is odd cycles, which break the easy structure of pairing problems in the way where the corners stop being whole described; Edmonds handled them by shrinking each odd cycle to a single point and expanding it later. With that, Edmonds and Ellis Johnson showed in 1973 that the postman problem is solved in polynomial time: shortest paths, a cheapest pairing, and a splice.

The pairing is a matching #

Stripped of streets, the choice the postman faces is this: a list of odd corners, a distance between every two of them, and the task of splitting the list into pairs so that the total distance is least. That is a minimum-weight perfect matching on a complete network whose vertices are the odd corners, and it is the same kind of object as the assignments of a price for every person and task — with one difference that turns out to matter.

In an assignment, the two sides are different: people on one side, tasks on the other, and every pair joins a person to a task. That bipartite structure is what makes the corners of the assignment problem whole, so that a linear program solves it outright, and what makes Hall’s theorem decide whether a complete assignment exists. The postman’s pairing has no two sides. Any odd corner may be paired with any other, and the network of possible pairs contains triangles and every other odd cycle. The linear program for matching then has fractional corners — a half on each edge of a triangle — and the easy theory fails exactly as it failed for matchings in graphs with odd cycles.

Edmonds’s algorithm is the repair. It runs the assignment method until an odd cycle blocks it, shrinks the cycle to a single point, carries on, and expands the cycle again at the end, choosing within it how the pairs fall. The number of shrinkings is bounded, and the whole procedure takes a number of steps polynomial in the number of corners. It was the first demonstration that a problem with an odd-cycle obstruction could still be solved quickly, and the postman problem was one of its first applications.

Where the problem turns hard #

The postman’s problem is easy because of a single fact: the repeated streets need only fix the parity of the corners, and parity is a local condition. Change the problem slightly and that fact goes, and with it the easy answer.

One-way streets. If every street is one-way, the condition for a round that walks each street once is that every corner has as many streets in as out, and the repeated streets must balance the surpluses. That is a flow problem, and the bottleneck is the whole story is about exactly that kind of problem: it is solved by a cheapest flow, still in polynomial time.

A mixture of one-way and two-way streets. Now each two-way street’s direction is a choice, and the choices interact. Christos Papadimitriou showed in 1976 that this mixed version is as hard as the standard hard problems: no fast method is known, and none is expected.

Only some streets need visiting. A snowplough must clear the main roads and may use side streets to get between them. This rural postman problem is hard as well, because deciding which side streets to use is a problem of connecting pieces, like a travelling salesman’s, and not merely of fixing parity. Its connection to the travelling salesman is direct: when the required streets are tiny and far apart, visiting them is a tour.

The pattern is the one a walk that changes one thing at a time met between edges and vertices. A condition that can be checked and repaired corner by corner gives an easy problem. A condition that couples distant parts of the network — which way a street runs, which pieces must be joined up — gives a hard one, and the line between them is sharp.

From a post office to a snowplough #

Kwan Mei-Ko’s paper of 1960 came out of a practical campaign to organise postal delivery, and his solution was the characterisation: a round is shortest exactly when its repeated streets pair up the odd corners and no cycle of repeated streets could be swapped for a shorter one. He gave a way of improving a round step by step until it satisfied that condition, which works but gives no bound on how many steps it takes. The polynomial method came thirteen years later, from the matching algorithm.

The applications are every service that must pass along streets rather than visit addresses: sweeping, gritting and snow clearing, refuse collection, meter reading, inspecting roads, rails or power lines. In all of them the length of street to be covered is fixed and the only saving is in the repeats, which is exactly the quantity the pairing minimises. In large networks the repeats are typically a modest fraction of the total — a city grid’s odd corners are only on its boundary, so the repeats scale with the perimeter while the streets scale with the area — and that fraction is what the planner is paid to reduce.

The real problems carry complications the pure version ignores: several vehicles instead of one, a limited load, streets that must be covered only in one direction, time windows. Each complication pushes the problem across the line described above, and the practical methods for them are heuristics built on the pure solution — pair the odd corners, splice a round, then cut it into pieces that respect the constraints.

What the maps cannot show #

Why no shorter round exists. Each figure draws one round and quotes its length as the minimum. The minimum is established by the parity argument — every round’s repeats pair up the odd corners — together with the exhaustive pricing of pairings. The drawing shows the round that achieves the bound; it cannot show the thousands of rounds that do not beat it.

Which round. A district has many shortest rounds: the pairing may not be unique, as Königsberg shows with its two cheapest pairings, and once the repeated streets are fixed the splicing construction can produce many different circuits. The figures draw the repeated streets and not the order of walking, because the order is where the many choices lie and none of them changes the length.

Real streets. A real postman crosses roads, has a bag that gets lighter, and cares about left turns. The problem drawn here measures only length, and the published versions that measure time, turns or load become different problems — most of them hard.

Still open: every edge in exactly two cycles #

A graph whose degrees are all even splits into cycles. A connected graph with every edge doubled has all degrees even, and so it splits into cycles too — but those cycles may use both copies of an edge in one cycle, which is walking it there and straight back. A much stronger statement has been conjectured since the 1970s, by George Szekeres and independently by Paul Seymour.

The cycle double cover conjecture: every graph with no bridge — no edge whose removal disconnects it — has a collection of cycles, each a closed path that repeats no vertex, covering every edge exactly twice. It is known for large families of graphs, including every graph that can be drawn on the plane without crossings and every graph with a circuit through all its vertices, and it has been checked on every small graph that has been searched. For general bridgeless graphs it is open. It asks for a postman’s doubling in which every repeated street belongs to a genuine loop, and it is one of the most studied unsolved problems in graph theory.

Parity, repaired as cheaply as possible #

A postman’s round must walk some streets twice exactly when some corners have odd degree, and the repeated streets always join those corners in pairs, because a closed walk enters and leaves every corner equally often. So the shortest round is every street once plus the cheapest pairing of the odd corners, found by pricing pairings through shortest paths.

Königsberg’s round is nine crossings; the three-by-three grid’s is twenty-eight blocks. Pairing the closest corners first can cost half as much again as the best pairing, and the right pairing is found by a matching algorithm whose one real difficulty is the odd cycle. Make some streets one-way or some streets optional, and parity stops being enough — and the problem stops being easy.