POLYTOPO - The Chinese Postman Problem

Topological curiosities

Beyond Intuition

Edges & Surfaces — Part 2 of 3

The Chinese Postman Problem

In Part 1, Euler proved that some walks are impossible: if a graph has more than two odd-degree vertices, you cannot traverse every edge exactly once. But a postman still has to deliver to every street. So: what is the shortest route that covers every edge — even if some must be walked twice? Kwan Mei-Ko answered this in 1960, turning Euler's impossibility theorem into a practical algorithm. The key insight: fix the odd-degree vertices, and the impossible becomes optimal.

The neighbourhood. 9 intersections, 12 streets, 1 050 m total. The post office is at P (top-left). Can the postman walk every street exactly once and return home?

Step 1 / 8

Try it on paper

Draw 9 dots and 12 lines matching the map. Try to trace every line without lifting your pen or repeating any. You will always get stuck — just as in Königsberg. Now count the degree of each dot. Find the odd-degree ones, pair them up, and add the shortest path between each pair. Try tracing again: now it works.

Kwan Mei-Ko, 1960

Chinese mathematician Kwan Mei-Ko posed and solved this problem in 1960 — the first practical application of Euler's 1736 theorem, turning a theoretical impossibility into a polynomial-time optimisation algorithm. The algorithm directly uses Hierholzer's method from Part 1 to find the Eulerian circuit once the odd-degree vertices are fixed.

From Königsberg to topology — and the bridge to Part 3

Parts 1 and 2 share the same protagonist: the degree of a vertex. In Part 1, odd degree blocked the walk entirely. In Part 2, odd degree tells you exactly where to add repeated edges and how many. Degree is a local property of a vertex, but it governs a global property of the whole route.

In Part 3 (Euler Characteristic), Euler turns this same combinatorial arithmetic — counting vertices, edges, and faces — toward a completely different question: what is the shape of a surface? The formula V − E + F = 2 for a sphere and V − E + F = 0 for a torus shows that counting edges (as we have been doing throughout) is enough to classify surfaces topologically. The postman's route and the shape of a donut are, at their mathematical core, the same kind of question.

Postal delivery — every postal service that plans optimised delivery rounds is solving this problem. The algorithm guarantees the shortest possible route covering every street.

Snow ploughing & street sweeping — city councils use the Chinese Postman algorithm to plan salt-spreading and refuse collection routes, minimising fuel and repeated driving.

Network inspection — testing every link in a power grid, water network, or fibre optic system is a Chinese Postman problem. The algorithm determines whether a single continuous inspection walk is possible, and if not, the minimum extra distance required.

The algorithm — and its connection to Parts 1 and 3

Given a connected graph where an Eulerian circuit does not exist (from Part 1: more than two odd-degree vertices):

Step 1. Identify all odd-degree vertices. There will always be an even number of them — a consequence of the handshaking lemma (sum of all degrees = 2E).

Step 2. Find the minimum-weight perfect matching of the odd vertices — pair them so the total extra distance is minimised.

Step 3. Add a duplicate of the shortest path between each matched pair. All vertices now have even degree — the obstruction from Part 1 is removed.

Step 4. Find the Eulerian circuit on the augmented graph using Hierholzer's algorithm (Part 1).

Total distance = sum of all edges + weight of minimum matching. The connection to Part 3: the handshaking lemma (sum of degrees = 2E) is the same identity that appears inside the proof of Euler's polyhedron formula V − E + F = 2 — edges counted from two directions always balance.

Königsberg Seven Bridges