IB Mathematics · Graph TheoryAI HL

Chinese Postman Problem

How to decide what must be repeated

The postman must cover every edge and finish where the route started. The first job is not to look at the weights. First count the degree of each vertex. The odd vertices tell us what has to be repeated. After that, the weights tell us the cheapest repetition.

CourseApplications and Interpretation HL

TopicChinese Postman Problem

Practice12 IB-style weighted graphs

The Method I Use

Start with the degrees. Do not search for a route immediately. Once the odd vertices are known, the problem falls into one of the three cases below.

Case 1

All vertices have even degree

The graph is Eulerian. Every edge can be used exactly once in one closed route.

So there is nothing extra to repeat. Find an Euler circuit and come back to the starting vertex.

Minimum cost = sum of all edge weights

Case 2

Exactly two vertices are odd

Find the shortest path joining the two odd vertices. Repeat that path once.

In the final route, the vertices and edges on that shortest path will appear again. The added cost comes from those repeated edges.

Minimum cost = total edge weight + shortest odd-to-odd path

Case 3

More than 2 odd vertices

For four odd vertices, make the three possible pairings. For each pair, use the shortest path between the two vertices.

Add the two shortest-path costs in each pairing. Choose the pairing with the smallest total. Repeat those two paths. Now every degree is even.

Minimum cost = total edge weight + smallest pairing cost

For more than four odd vertices: the same idea continues. Pair all the odd vertices so that the total cost of the repeated shortest paths is as small as possible. In the IB questions here, the important case is usually four odd vertices.

Quick Technique

Count the degree of every vertex. Ignore the weights for this step.
Add all the edge weights. This is the starting cost.
Look at the number of odd vertices: 0, 2, or more than 2.
If there are two odd vertices, repeat the cheapest path joining them.
If there are four odd vertices, compare the three pairings and repeat the pair of paths with the least extra cost.
After the repetition, every vertex must have even degree. Then trace an Euler circuit.

Degree decides the case. Weight decides what to repeat.

Practice Problems

12 questions · 3 cases

Chinese Postman Problem

Case 1: Eulerian

All degrees even

Find the minimum total weight of a closed route that uses every edge at least once and returns to the starting vertex. Also give one optimal route starting from A.

Weighted graph for Chinese Postman Question 1 — Question 1: weighted graph

Show SolutionHide Solution

Solution

Case 1: Eulerian

Step 1: Check the degrees. Every vertex has even degree. So no extra edge has to be repeated.

Step 2: Add the original edge weights.

Minimum cost = 41

Step 3: Trace an Euler circuit. One possible route from A is:

A → E → F → D → C → B → D → E → B → A

Minimum total weight = 41

Chinese Postman Problem

Case 1: Eulerian

All degrees even

Find the minimum total weight of a closed route that uses every edge at least once and returns to the starting vertex. Also give one optimal route starting from A.

Weighted graph for Chinese Postman Question 2 — Question 2: weighted graph

Show SolutionHide Solution

Solution

Case 1: Eulerian

Step 1: Check the degrees. Every vertex has even degree. So no extra edge has to be repeated.

Step 2: Add the original edge weights.

Minimum cost = 47

Step 3: Trace an Euler circuit. One possible route from A is:

A → F → E → D → F → B → D → C → B → A

Minimum total weight = 47

Chinese Postman Problem

Case 1: Eulerian

All degrees even

Find the minimum total weight of a closed route that uses every edge at least once and returns to the starting vertex. Also give one optimal route starting from A.

Weighted graph for Chinese Postman Question 3 — Question 3: weighted graph

Show SolutionHide Solution

Solution

Case 1: Eulerian

Step 1: Check the degrees. Every vertex has even degree. So no extra edge has to be repeated.

Step 2: Add the original edge weights.

Minimum cost = 64

Step 3: Trace an Euler circuit. One possible route from A is:

A → D → C → E → D → B → E → A → C → B → A

Minimum total weight = 64

Chinese Postman Problem

Case 1: Eulerian

All degrees even

Find the minimum total weight of a closed route that uses every edge at least once and returns to the starting vertex. Also give one optimal route starting from A.

Weighted graph for Chinese Postman Question 4 — Question 4: weighted graph

Show SolutionHide Solution

Solution

Case 1: Eulerian

Step 1: Check the degrees. Every vertex has even degree. So no extra edge has to be repeated.

Step 2: Add the original edge weights.

Minimum cost = 53

Step 3: Trace an Euler circuit. One possible route from A is:

A → E → D → C → E → F → G → A → C → B → A

Minimum total weight = 53

Chinese Postman Problem

Case 2: Two odd vertices

Repeat one shortest path

Find the minimum total weight of a closed route that uses every edge at least once and returns to the starting vertex. Also give one optimal route starting from A.

Weighted graph for Chinese Postman Question 5 — Question 5: weighted graph

Show SolutionHide Solution

Solution

Case 2: Two odd vertices

Step 1: Find the odd vertices. The odd vertices are E and F.

Step 2: Find the cheapest way to join them. The shortest path is E → D → F, with cost 18.

This is the part we repeat. After repeating this path, the two odd vertices become even.

Step 3: Add the repeated cost.

51 + 18 = 69

Step 4: Trace the closed route. One possible optimal route from A is:

A → E → D → F → D → C → B → D → E → B → A

Minimum total weight = 69

Chinese Postman Problem

Case 2: Two odd vertices

Repeat one shortest path

Find the minimum total weight of a closed route that uses every edge at least once and returns to the starting vertex. Also give one optimal route starting from A.

Weighted graph for Chinese Postman Question 6 — Question 6: weighted graph

Show SolutionHide Solution

Solution

Case 2: Two odd vertices

Step 1: Find the odd vertices. The odd vertices are B and D.

Step 2: Find the cheapest way to join them. The shortest path is B → F → E → D, with cost 8.

This is the part we repeat. After repeating this path, the two odd vertices become even.

Step 3: Add the repeated cost.

37 + 8 = 45

Step 4: Trace the closed route. One possible optimal route from A is:

A → F → E → D → E → F → B → F → D → C → B → A

Minimum total weight = 45

Chinese Postman Problem

Case 2: Two odd vertices

Repeat one shortest path

Find the minimum total weight of a closed route that uses every edge at least once and returns to the starting vertex. Also give one optimal route starting from A.

Weighted graph for Chinese Postman Question 7 — Question 7: weighted graph

Show SolutionHide Solution

Solution

Case 2: Two odd vertices

Step 1: Find the odd vertices. The odd vertices are B and E.

Step 2: Find the cheapest way to join them. The shortest path is B → C → E, with cost 7.

This is the part we repeat. After repeating this path, the two odd vertices become even.

Step 3: Add the repeated cost.

56 + 7 = 63

Step 4: Trace the closed route. One possible optimal route from A is:

A → D → C → E → D → B → C → E → A → C → B → A

Minimum total weight = 63

Chinese Postman Problem

Case 2: Two odd vertices

Repeat one shortest path

Find the minimum total weight of a closed route that uses every edge at least once and returns to the starting vertex. Also give one optimal route starting from A.

Weighted graph for Chinese Postman Question 8 — Question 8: weighted graph

Show SolutionHide Solution

Solution

Case 2: Two odd vertices

Step 1: Find the odd vertices. The odd vertices are A and G.

Step 2: Find the cheapest way to join them. The shortest path is A → E → F → G, with cost 23.

This is the part we repeat. After repeating this path, the two odd vertices become even.

Step 3: Add the repeated cost.

54 + 23 = 77

Step 4: Trace the closed route. One possible optimal route from A is:

A → E → F → G → F → E → D → C → E → A → C → B → A

Minimum total weight = 77

Chinese Postman Problem

Case 3: More than 2 odd vertices

Choose the best pairing

Find the minimum total weight of a closed route that uses every edge at least once and returns to the starting vertex. Also give one optimal route starting from A.

Weighted graph for Chinese Postman Question 9 — Question 9: weighted graph

Show SolutionHide Solution

Solution

Case 3: More than 2 odd vertices

Step 1: Find the odd vertices. They are B, D, E, F.

Step 2: Pair the odd vertices. With four odd vertices there are three possible pairings. For each pairing, use the shortest path between the paired vertices.

Pairing	Shortest paths	Extra cost
B with E D with F	B → E = 5 D → F = 2	5 + 2 = 7
B with D E with F	B → C → D = 9 E → D → F = 7	9 + 7 = 16
B with F E with D	B → C → D → F = 11 E → D = 5	11 + 5 = 16

Step 3: Choose the smallest extra cost. The best pairing is B with E, and D with F. The repeated cost is 7.

37 + 7 = 44

Step 4: Trace the Euler circuit after repeating those paths. One possible optimal route from A is:

A → E → D → F → D → C → B → E → B → A

Minimum total weight = 44

Chinese Postman Problem

Case 3: More than 2 odd vertices

Choose the best pairing

Find the minimum total weight of a closed route that uses every edge at least once and returns to the starting vertex. Also give one optimal route starting from A.

Weighted graph for Chinese Postman Question 10 — Question 10: weighted graph

Show SolutionHide Solution

Solution

Case 3: More than 2 odd vertices

Step 1: Find the odd vertices. They are A, B, D, E.

Step 2: Pair the odd vertices. With four odd vertices there are three possible pairings. For each pairing, use the shortest path between the paired vertices.

Pairing	Shortest paths	Extra cost
B with D E with A	B → D = 5 E → F → A = 9	5 + 9 = 14
B with E D with A	B → F → E = 11 D → F → A = 10	11 + 10 = 21
B with A D with E	B → F → A = 8 D → F → E = 13	8 + 13 = 21

Step 3: Choose the smallest extra cost. The best pairing is B with D, and E with A. The repeated cost is 14.

41 + 14 = 55

Step 4: Trace the Euler circuit after repeating those paths. One possible optimal route from A is:

A → F → E → F → D → B → D → C → B → F → A

Minimum total weight = 55

Chinese Postman Problem

Case 3: More than 2 odd vertices

Choose the best pairing

Find the minimum total weight of a closed route that uses every edge at least once and returns to the starting vertex. Also give one optimal route starting from A.

Weighted graph for Chinese Postman Question 11 — Question 11: weighted graph

Show SolutionHide Solution

Solution

Case 3: More than 2 odd vertices

Step 1: Find the odd vertices. They are A, B, C, D.

Step 2: Pair the odd vertices. With four odd vertices there are three possible pairings. For each pairing, use the shortest path between the paired vertices.

Pairing	Shortest paths	Extra cost
A with B C with D	A → B = 9 C → E → D = 8	9 + 8 = 17
A with C B with D	A → E → C = 10 B → E → D = 9	10 + 9 = 19
A with D B with C	A → D = 10 B → C = 8	10 + 8 = 18

Step 3: Choose the smallest extra cost. The best pairing is A with B, and C with D. The repeated cost is 17.

55 + 17 = 72

Step 4: Trace the Euler circuit after repeating those paths. One possible optimal route from A is:

A → D → E → D → C → E → C → B → E → A → B → A

Minimum total weight = 72

Chinese Postman Problem

Case 3: More than 2 odd vertices

Choose the best pairing

Find the minimum total weight of a closed route that uses every edge at least once and returns to the starting vertex. Also give one optimal route starting from A.

Weighted graph for Chinese Postman Question 12 — Question 12: weighted graph

Show SolutionHide Solution

Solution

Case 3: More than 2 odd vertices

Step 1: Find the odd vertices. They are B, C, E, F.

Step 2: Pair the odd vertices. With four odd vertices there are three possible pairings. For each pairing, use the shortest path between the paired vertices.

Pairing	Shortest paths	Extra cost
B with C E with F	B → A → C = 15 E → C → A → G → F = 24	15 + 24 = 39
B with E C with F	B → A → C → E = 19 C → A → G → F = 20	19 + 20 = 39
B with F C with E	B → A → G → F = 25 C → E = 4	25 + 4 = 29

Step 3: Choose the smallest extra cost. The best pairing is B with F, and C with E. The repeated cost is 29.

58 + 29 = 87

Step 4: Trace the Euler circuit after repeating those paths. One possible optimal route from A is:

A → E → C → E → D → C → A → G → F → G → A → B → A

Minimum total weight = 87

Chinese Postman Problem

The Method I Use

All vertices have even degree

Exactly two vertices are odd

More than 2 odd vertices

Quick Technique

Practice Problems

Chinese Postman Problem

Solution

Chinese Postman Problem

Solution

Chinese Postman Problem

Solution

Chinese Postman Problem

Solution

Chinese Postman Problem

Solution

Chinese Postman Problem

Solution

Chinese Postman Problem

Solution

Chinese Postman Problem

Solution

Chinese Postman Problem

Solution

Chinese Postman Problem

Solution

Chinese Postman Problem

Solution

Chinese Postman Problem

Solution

Available Formula Sheets