What Is the Chinese Postman Problem and How Do You Solve It?

The Chinese postman problem asks for the shortest closed route that traverses every edge of a connected, weighted, undirected graph at least once. Solve it by duplicating the minimum-weight combination of edges needed to make every vertex even, then finding an Eulerian circuit.

This is HL-only content from AHL 3.16: Tree and cycle algorithms, Chinese postman, travelling salesman.

The Method

1. Add the weights of all edges. This is the route length if every edge can be used exactly once.
2. Identify all odd vertices: vertices with an odd degree. There must be an even number of them.
3. Find the shortest paths between pairs of odd vertices.
4. Choose the pairing with the smallest total weight. In IB questions, there will be no more than four odd vertices.
5. Duplicate the edges along those shortest paths. The affected vertices then have even degree.
6. Construct an Eulerian circuit through the augmented graph. The route must start and finish at the same vertex.

Suppose the total weight of the original graph is $42$, and its four odd vertices are $A$, $B$, $C$, and $D$. The shortest-path pairings are:

The minimum duplication weight is $10$, so the minimum Chinese postman route has weight

$$42+10=52.$$

A common misconception is that this is the travelling salesman problem. It is not: the Chinese postman problem covers every edge, whereas the travelling salesman problem visits every vertex and returns to the start.

Exam Technique

For a command such as determine, show the odd vertices, all possible pairings, the selected minimum pairing, and the calculation $\text{original weight}+\text{duplicated weight}$. A final route length alone may not demonstrate the required algorithm or justify why the route is minimal.