The Chinese Postman

A mail carrier leaves the post office, has to walk down every street in the neighborhood to deliver the mail, and then returns to where they started. The question is simple to state: what is the shortest route that covers every street and ends back home?

This is the Chinese Postman Problem, named after the Chinese mathematician Kwan Mei-Ko, who posed it in 1960. It sounds almost identical to the famous traveling salesman, who must visit every city — and that one is notoriously, provably hard.

But there is a twist. The postman cares about streets (the edges of the map), not cities (the points). And that single change flips the problem from one of the hardest we know to one we can solve quickly and exactly, every time.

Here is a small street map. The postman must traverse every street at least once and finish back at the start. If you could walk each street exactly once you'd be done with no wasted steps — but that is only possible when every junction has an even number of streets meeting at it.

<p class="hint">{{hint}}</p>
<svg id="map" viewBox="0 0 320 230" aria-label="{{map_aria}}"></svg>
<div class="status" id="status">{{status_initial}}</div>
<div class="btns">
  <button id="solve" type="button">{{btn_solve}}</button>
  <button id="reset" type="button" class="ghost">{{btn_reset}}</button>
</div>

* { box-sizing: border-box; }
body { font-family: system-ui, sans-serif; color: #222; margin: 0; }
.hint { font-size: .9rem; color: #444; margin: 0 0 .6rem; line-height: 1.45; }
#map { width: 100%; max-width: 360px; height: auto; display: block; margin: 0 auto; }
.edge { stroke: #9aa3ad; stroke-width: 4; stroke-linecap: round; }
.edge.dup { stroke: #e63946; stroke-width: 8; }
.node { fill: #1d3557; }
.node.odd { fill: #f4a261; stroke: #c97b29; stroke-width: 2; }
.nlabel { font: 700 12px ui-monospace, monospace; fill: #fff; text-anchor: middle; dominant-baseline: central; }
.wlabel { font: 600 11px ui-monospace, monospace; fill: #4a5560; text-anchor: middle; }
.status { font-size: 1rem; font-weight: 600; margin: .6rem 0 .4rem; min-height: 1.4em; }
.status.ok { color: #0a7d33; }
.btns { display: flex; gap: .5rem; flex-wrap: wrap; }
button { font: 600 14px system-ui, sans-serif; padding: .45rem .9rem; border: 1px solid #1d3557;
         background: #1d3557; color: #fff; border-radius: 8px; cursor: pointer; }
button.ghost { background: #fff; color: #1d3557; }

// Code not found

Press Solve optimally and watch the trick. The algorithm finds the junctions with an odd number of streets, pairs them up as cheaply as possible, and marks those connecting paths to be walked twice. Everything else is walked once. The total — every street plus the few unavoidable repeats — is provably the shortest covering route there is.

The Chinese Postman looks like it should be intractable, yet it is one of the happy surprises of complexity theory.

• Status: solved, in polynomial time. In 1973 Jack Edmonds and Ellis Johnson gave an efficient exact algorithm. There is no exponential blow-up and no guessing.
• The key idea. A route that uses every street exactly once (an Euler tour) exists precisely when every junction has even degree. The only obstacle is the junctions with odd degree — and by a classic theorem there is always an even number of them.
• Reduce to matching. Pair up the odd junctions and add a shortest detour between each pair; those detours are the streets you must repeat. Choosing the cheapest way to pair them is a minimum-weight matching problem, which Edmonds himself showed can be solved in polynomial time.
• Contrast with TSP. The traveling salesman must visit every vertex and is NP-hard — no known fast algorithm. Switching "visit every city" to "cover every street" moves the problem from the hardest tier to the easy one.

That is the punchline: two problems that sound like twins sit on opposite sides of the great divide of P vs NP. Covering edges is easy; visiting nodes is hard.

"Cover every edge of a network with the least travel" — known as arc routing — is everywhere once you look for it:

• Municipal services: snow plowing, street sweeping, garbage collection and gritting all need every street covered, not every address visited.
• Utilities and delivery: meter reading, mail rounds and newspaper routes are classic postman tours.
• Inspection: walking or flying a drone along every power line, pipeline or rail segment to check for faults.
• Maintenance planning: line painting, leaf removal and patrol routes that must sweep an entire road network.

Because the problem is solved exactly and fast, these routes can be optimized for real city-sized maps. The lesson is broader than logistics: a tiny change in what you must cover — edges instead of nodes — can decide whether a problem joins the easy P vs NP winners or the intractable traveling salesman losers.

The Chinese Postman is a rare gift: a real, useful routing problem that we can solve perfectly and quickly. The whole difficulty collapses into one elegant move — find the odd junctions, match them cheaply, and repeat exactly those streets.

It is also a perfect illustration of how delicate the boundary of difficulty is. Ask the postman to cover every street and the answer is fast and exact; ask the salesman to visit every city and you fall straight into the traveling salesman and the open mystery of P vs NP. Same map, one word changed, opposite worlds.