The Chinese Postman Problem

A mail carrier has to walk along every street on their route and return to the post office. A snowplough, a street sweeper and a road inspector have the same job. What is the shortest route that covers every edge of a weighted graph at least once and returns to the start? This is the Chinese postman problem (also called the route inspection problem), first posed by the Chinese mathematician Kwan Mei-Ko in 1962.

Key ideas

When no edges need repeating

If every vertex of a connected graph is even, the graph has an Eulerian circuit: a closed route using every edge exactly once. That route is clearly the shortest possible, so

$$\text{shortest route} = \text{total weight of all the edges}$$

Why odd vertices force repeats

At an odd vertex, the route can’t pair every arrival with a departure along a new edge, so some edges at that vertex must be travelled twice. Repeating an edge is the same as adding a copy of it to the graph. We want to add copies so that every vertex becomes even, as cheaply as possible.

Adding copies along a path from one odd vertex to another changes the degree of those two end vertices by $1$ (making them even) and of every vertex in between by $2$ (keeping them even). So the cheapest fix is to pair up the odd vertices and repeat the shortest path between each pair. The new graph has an Eulerian circuit, and that circuit is the postman’s route.

The algorithm

1. List the odd vertices. If there are none, the answer is the total weight.
2. List every way of pairing them up.
   • With $2$ odd vertices, say X and Y, there’s only one pairing: XY.
   • With $4$ odd vertices W, X, Y, Z, there are three: WX and YZ; WY and XZ; WZ and XY.
3. For each pairing, find the shortest path between each pair (by inspection, checking possible routes) and add the lengths.
4. Choose the pairing with the smallest total. Repeat the edges on those shortest paths.
5. Shortest route length $=$ total weight of all edges $+$ the smallest pairing total. Find an actual route as an Eulerian circuit of the graph with the repeated edges added.

The IB course uses graphs with up to four odd vertices.

A variation: start and finish at different vertices

Sometimes the route doesn’t have to return to its start. Then two odd vertices can be the start and finish, and they don’t need pairing.

• With $2$ odd vertices: start at one, finish at the other. Nothing is repeated, so the length is just the total weight.
• With $4$ odd vertices: you still pair two of them. Repeat the single shortest of the six possible odd-to-odd paths, and start and finish at the other two odd vertices.

Worked examples

Example 1: Two odd vertices

A road inspector must drive along every road in a network and return to the depot at A. The roads, with lengths in km, are AB $6$, AC $8$, BC $3$, BD $7$, CD $5$, CE $9$, DE $4$, DF $6$ and EF $5$. Find the length of the shortest inspection route.

Solution. Total length of all roads:

$$6 + 8 + 3 + 7 + 5 + 9 + 4 + 6 + 5 = 53 \text{ km}$$

Degrees: A $2$, B $3$, C $4$, D $4$, E $3$, F $2$. The odd vertices are B and E, so there’s one pairing: BE.

Shortest path from B to E (there’s no direct road): B–D–E is $7 + 4 = 11$, B–C–E is $3 + 9 = 12$, and B–C–D–E is $3 + 5 + 4 = 12$. The shortest is B–D–E, $11$ km.

Repeat BD and DE. The shortest route is $53 + 11 = 64$ km.

Example 2: Four odd vertices

The odd vertices A, B, D and E are highlighted.

Find the shortest route that travels along every edge of the graph above at least once and returns to its starting point. Write down one such route starting at A.

Solution. Total weight: $4 + 6 + 9 + 5 + 8 + 3 + 7 + 5 + 4 = 51$.

Degrees: A $3$, B $3$, C $4$, D $3$, E $3$, F $2$. There are four odd vertices: A, B, D, E.

Find the shortest path between each pair of odd vertices:

Pair	Shortest path	Length
AB	A–B	4
DE	D–F–E	9
AD	A–D (or A–C–D)	9
BE	B–E	8
AE	A–B–E	12
BD	B–C–D	8

Now compare the three pairings:

Pairing	Total
AB and DE	$4 + 9 = 13$
AD and BE	$9 + 8 = 17$
AE and BD	$12 + 8 = 20$

The best pairing is AB and DE, so repeat AB, DF and FE. The shortest route has length

$$51 + 13 = 64$$

Repeating AB, DF and FE makes every vertex even.

With the repeats, every vertex has degree $4$, so there’s an Eulerian circuit. One route from A:

$$\text{A–B–A–C–B–E–F–E–C–D–F–D–A}$$

Check: it uses $12$ edges (the $9$ original edges plus the $3$ repeats), and its length is $64$.

Example 3: Finishing somewhere else

For the graph in Example 2, the route may now start and finish at different vertices. Find the length of the shortest route, and where it must start and finish.

Solution. Two of the odd vertices can be the start and finish; the other two must be joined by a repeated shortest path. From the table in Example 2, the shortest odd-to-odd path is AB, length $4$.

So repeat AB, and start at D and finish at E (or the reverse). The shortest route is

$$51 + 4 = 55$$

Common mistakes

Repeating the direct edge when a shorter path exists. In Example 2, D and E aren’t even adjacent, and in other graphs the direct edge between two odd vertices can be longer than a route through another vertex. Always check the alternatives.

Checking only one pairing. With four odd vertices there are three pairings, and the best one isn’t always the one with the single shortest path. Work out all three totals.

Forgetting the total weight. The answer is the total of all the edges plus the repeated paths, not just the repeats.

Pairing even vertices. Only the odd vertices need fixing. Vertices in the middle of a repeated path stay even.

Mixing up the closed and open versions. If the route must return to its start, pair all the odd vertices. If it can finish elsewhere, two odd vertices become the ends and only one pair gets a repeated path.

Practice

1. (Warm-up) A graph has edges AB $5$, BC $7$, CA $6$, CD $4$, DE $3$ and EC $8$. Find the length of the shortest closed route that travels every edge.

Solution

Degrees: A $2$, B $2$, C $4$, D $2$, E $2$. All even, so there’s an Eulerian circuit and nothing needs repeating:

$$5 + 7 + 6 + 4 + 3 + 8 = 33$$

2. (Warm-up) A graph has exactly four odd vertices, P, Q, R and S. List all the possible pairings.

Solution

PQ and RS; PR and QS; PS and QR. (P must be paired with one of the other three, and that decides the second pair.)

3. (Warm-up) A connected graph has total weight $40$. Its only odd vertices are X and Y, and the shortest path between them has length $4$. What is the length of the shortest closed route that travels every edge?

Solution

Repeat the shortest X–Y path: $40 + 4 = 44$.

4. (Core) A park has paths PQ $6$, PR $9$, QR $4$, QS $8$, RS $5$, RT $7$ and ST $3$ (in hundreds of metres). A ranger must walk every path and return to the start. Find the length of the shortest route, and which path(s) are walked twice.

Solution

Total: $6 + 9 + 4 + 8 + 5 + 7 + 3 = 42$.

Degrees: P $2$, Q $3$, R $4$, S $3$, T $2$. Odd vertices Q and S.

Shortest Q–S path: direct QS is $8$; Q–R–S is $4 + 5 = 9$. So repeat QS.

Shortest route: $42 + 8 = 50$ hundred metres, which is $5$ km, with path QS walked twice.

5. (Core) A graph has edges AB $3$, AC $8$, BC $4$, BD $7$, CD $2$, CE $5$ and DE $7$. Find the length of the shortest closed route that travels every edge, and say which edges are repeated.

Solution

Total: $3 + 8 + 4 + 7 + 2 + 5 + 7 = 36$.

Degrees: A $2$, B $3$, C $4$, D $3$, E $2$. Odd vertices B and D.

Shortest B–D path: direct BD is $7$, but B–C–D is $4 + 2 = 6$. So repeat BC and CD.

Shortest route: $36 + 6 = 42$.

6. (Core) A graph has edges AB $10$, AC $4$, BC $5$, BD $3$, CD $8$, AE $6$, CE $7$ and DE $9$. Find the length of the shortest closed route that travels every edge.

Solution

Total: $10 + 4 + 5 + 3 + 8 + 6 + 7 + 9 = 52$.

Degrees: A $3$, B $3$, C $4$, D $3$, E $3$. Odd vertices A, B, D, E.

Shortest paths: AB $9$ (A–C–B, shorter than the direct $10$), DE $9$, AD $12$ (A–C–D or A–C–B–D), BE $12$ (B–C–E or B–D–E), AE $6$, BD $3$.

Pairing	Total
AB and DE	$9 + 9 = 18$
AD and BE	$12 + 12 = 24$
AE and BD	$6 + 3 = 9$

Repeat AE and BD. Shortest route: $52 + 9 = 61$.

7. (Core) For the graph in Question 6, the route may start and finish at different vertices. Find the length of the shortest route that travels every edge, and where it starts and finishes.

Solution

Repeat only the single shortest odd-to-odd path, which is BD ($3$), and start and finish at the other two odd vertices, A and E.

Shortest route: $52 + 3 = 55$, starting at A and finishing at E (or the reverse).

8. (Challenge) In the graph of Example 2, the weight of edge AB is changed from $4$ to $x$, where $x \gt 0$. For which values of $x$ is pairing AB and DE still the best choice? Find the length of the shortest closed route in terms of $x$ for those values.

Solution

The shortest A–B path is now the smaller of $x$ and A–C–B $= 6 + 5 = 11$. Compare the three pairings when $x \lt 11$:

• AB and DE: $x + 9$.
• AD and BE: B–E is still $8$, and A–D is the smaller of $9$ and A–B–C–D $= x + 8$. The total is the smaller of $17$ and $x + 16$.
• AE and BD: B–D is still $8$ (B–C–D), and A–E is the smaller of $13$ (A–C–E) and $x + 8$ (A–B–E). The total is the smaller of $21$ and $x + 16$.

Since $x + 9 \lt x + 16$ always, AB and DE is best exactly when $x + 9 \lt 17$, that is, $x \lt 8$. (At $x = 8$ it ties with AD and BE; for $x \gt 8$, AD and BE is better.)

For $0 \lt x \lt 8$: total weight is $47 + x$, so the shortest route is

$$(47 + x) + (x + 9) = 56 + 2x$$

Check: $x = 4$ gives $64$, matching Example 2.

9. (Challenge) Explain why, in the Chinese postman algorithm, the repeated edges should form shortest paths joining the odd vertices in pairs, and why the resulting route is the shortest possible.

Solution

Think of the repeated edges as extra copies added to the graph. A closed route covering every edge exactly once in the new graph exists only if every vertex is even. The extra copies must therefore add an odd number of edges at each odd vertex and an even number at each even vertex. Any set of extra edges with this property can be split into trails that join the odd vertices in pairs (plus possibly some closed circuits, which only add length). So every possible route repeats, at the least, a set of paths joining the odd vertices in pairs. The cheapest way to join a given pair is a shortest path, and checking every pairing finds the cheapest overall. The route can’t be shorter than the total of all edges plus this cheapest set of repeats, and the Eulerian circuit of the new graph achieves exactly that length, so it’s the shortest route.