Chinese Postman Problem¶

Definition¶

The Chinese postman problem (CPP) finds a minimum-length closed route traversing every edge at least once in a connected undirected network with nonnegative edge lengths. To solve the course version, find a minimum-cost pairing of the odd-degree vertices using shortest-path distances, duplicate the corresponding paths, and construct an Euler tour in the resulting network.

Interpretation¶

The Chinese postman problem asks for the shortest closed route that covers every edge at least once, like a postman who must walk every street and return to the post office. Without an Euler tour, which would use every edge exactly once, some edges must be repeated, and the question becomes which repetitions add the least length.

A network of four vertices with edge lengths, where A and C have odd degree; the edge between them is duplicated so that a closed route can use every edge.

In the figure $A$ and $C$ have degree $3$ and $B$ and $D$ degree $2$ , so by the Euler network characterization there is no Euler tour. Duplicating the edge $A-C$ (dashed) raises both odd degrees to $4$ ; now every degree is even, and an Euler tour of the enlarged network covers all edges with length $14+4=18$ $18$ .

A closed route leaves every vertex as often as it arrives there, so it uses an even number of edge ends at each vertex, and an odd-degree vertex forces at least one repeated edge. Duplicating a path between two odd vertices makes both endpoints even and leaves the parity of the vertices in between unchanged, so the odd vertices are paired, each pair costing its shortest-path distance. Such a pairing exists because the number of odd vertices is even: each edge adds $2$ to the sum of all degrees.

The pairs are chosen jointly by a minimum-weight perfect matching, because pairing the closest odd vertices first can give a larger total than the best pairing.

Key Results¶

If every vertex already has even degree, any Euler tour is optimal.
The optimal cost is the sum of original edge lengths plus the minimum pairing cost.
The shortest path between paired vertices can contain intermediate vertices.

Examples¶

In the figure, $A$ and $C$ are the two odd-degree vertices. Their direct edge costs 4, compared with $2+3=5$ via $D$ or $3+2=5$ via $B$ . Duplicating the direct edge gives route length $14+4=18$ $18$ . The dashed edge denotes this extra copy.

The five-vertex example has total edge length 25 and minimum pairing cost 7, giving CPP value 32.
Pairing A with D duplicates A-C-D, while pairing B with E duplicates B-E.

Prerequisites¶

Euler Tour Algorithm

Sources¶

OR Modelling · Week 4

Aliases: route inspection problem, CPP, postman problem

Last updated: 20 October 2026 03:02