IB Maths AI HL Graph Theory Paper 1 & 2 Eulerian trails & circuits ~9 min read

Chinese Postman Problem

The Chinese Postman Problem (CPP) asks: what’s the shortest closed route that walks along every edge of a graph at least once? The answer depends entirely on how many odd-degree vertices the graph has. If every vertex is even, an Eulerian circuit exists — the route weight equals the total edge weight, no repeats needed. If there are odd vertices, you must repeat some edges — and the goal is to repeat the smallest total weight.

📘 What you need to know

Eulerian trail: a trail that uses every edge exactly once (vertices may repeat).
Eulerian circuit: an Eulerian trail that starts and ends at the same vertex.
Eulerian graph: has an Eulerian circuit ⇔ every vertex has even degree.
Semi-Eulerian graph: has an Eulerian trail but no circuit ⇔ exactly 2 odd-degree vertices (start and end of the trail).
Chinese Postman Problem (CPP): find the shortest closed route that traverses every edge at least once. Some edges may need to be repeated; minimise the total weight of those repeats.
Total CPP route weight = weight(G) + (total weight of repeated edges).
3 cases by odd vertex count: 0 odd → no repeats; 2 odd → repeat shortest path between them; 4 odd → try the 3 possible pairings and pick the smallest total.
Open variant (start and end at different vertices): with 2 odd vertices, start at one and end at the other — no repetition needed at all.
IB exam cap: questions never have more than 4 odd-degree vertices.

Eulerian trails and circuits

Here’s the classic puzzle: can you draw a shape without lifting your pen and without going over any line twice? If yes, your pen has traced an Eulerian trail. If you also finish where you started, it’s an Eulerian circuit. The remarkable fact — first noticed by Leonhard Euler in 1736 with the Königsberg bridges — is that you can decide whether such a path exists just by counting odd-degree vertices:

0 odd vertices → an Eulerian circuit exists (closed loop possible).
2 odd vertices → an Eulerian trail exists, but it must start at one odd vertex and finish at the other (no loop back to the start).
4 or more odd vertices → no single-pen drawing exists at all.

Why does this work? Every time the trail enters a vertex it must also leave, using two edges. So at every “pass-through” vertex, the count of edges used must be even — meaning the vertex must have even degree. Only the start and the end can break this rule (one unmatched edge each), and that’s exactly where the odd vertices live.

Memory tip: 0 odd ⇒ circuit (closed); 2 odd ⇒ trail (open); 4+ odd ⇒ impossible in one stroke. And by the Handshaking Lemma, the number of odd vertices is always even — never 1, 3, or 5.

The Chinese Postman Problem

Now flip the question. A postman has to walk every road (edge) at least once and return home — but unlike the Eulerian setting, he’s allowed to walk down the same road more than once. His goal: minimise total walking distance. This is the Chinese Postman Problem, first posed by Chinese mathematician Mei-Ko Kwan in 1962.

If the graph happens to have all even-degree vertices, the postman simply walks an Eulerian circuit — total distance = graph’s total weight, nothing repeated. But if any vertices are odd, he can’t avoid repeating some edges. The clever insight: repeating an edge adds 1 to the degree of each of its endpoints. So by choosing the right edges to repeat, you can turn every odd vertex into an even one — and then an Eulerian circuit exists on this “augmented” graph.

A graph with two odd-degree vertices (B and C, orange). The shortest path between them is the direct edge BC of weight 6, so this edge is repeated. Total CPP route = 33 (graph weight) + 6 (repeated edge) = 39.

Chinese Postman route length total route = weight(G) + (sum of repeated-edge weights) repeated edges = shortest path between the odd vertices (2 odd) or cheapest pairing (4 odd)

The three cases laid out

Number of odd vertices	What to do	CPP route length
0	Walk an Eulerian circuit — no repeats needed.	weight(G)
2 (call them u, v)	Repeat the edges along the shortest path from u to v.	weight(G) + d(u, v)
4 (A, B, C, D)	Compute the 3 possible pairings: AB+CD, AC+BD, AD+BC. Pick the smallest total; repeat those paths.	weight(G) + smallest pairing total

Open route variant — different start and end

Some questions allow the postman to start at one vertex and end at another. The rules adjust:

0 odd vertices: same as before — walk an Eulerian circuit. Route weight = weight(G).
2 odd vertices: even better — just start at one and end at the other. No repetition needed; route weight = weight(G).
4 odd vertices: pair up two of them (repeat the shortest path between that pair) and start/end at the other two. Route weight = weight(G) + cheapest single shortest path between any pair.

🧭 Recipe — solving any Chinese Postman question

Find the degree of every vertex; list the odd ones.
Count odd vertices: this picks the case (0, 2, or 4) you’re in.
Compute the total weight of the graph by summing every edge once.
Find repeated edges:
- 0 odd → none.
- 2 odd → shortest path between them.
- 4 odd → smallest of the 3 pairing totals.
Total CPP route = weight(G) + sum of repeated edges. If asked, construct a valid route by tracing an Eulerian circuit through the augmented graph.

Worked examples

WE 1

Determining whether an Eulerian circuit exists

A graph G has vertices { A, B, C, D, E } with edges AB, AC, AD, BC, BE, CD, CE, DE. Does G contain an Eulerian circuit, an Eulerian trail, or neither?

find each degree deg(A) = 3 (AB, AC, AD) deg(B) = 3 (AB, BC, BE) deg(C) = 4 (AC, BC, CD, CE) deg(D) = 3 (AD, CD, DE) deg(E) = 3 (BE, CE, DE) count odd vertices A, B, D, E are odd → 4 odd vertices neither Eulerian circuit nor Eulerian trail exists circuit needs 0 odd vertices; trail needs exactly 2. With 4 odd, neither works — the postman must repeat edges.

WE 2

All-even graph — no repeats needed

A graph has vertices { P, Q, R, S } and weighted edges PQ(4), QR(5), RS(6), SP(7), PR(3), QS(2). Verify that the graph is Eulerian, and find the shortest closed postman route.

degrees deg(P) = 3 (PQ, SP, PR) — odd! wait — recount carefully deg(P) = PQ, SP, PR = 3 (odd) deg(Q) = PQ, QR, QS = 3 (odd) deg(R) = QR, RS, PR = 3 (odd) deg(S) = RS, SP, QS = 3 (odd) all 4 odd — not Eulerian graph is not Eulerian (4 odd vertices) K₄ (complete graph on 4 vertices) always has every vertex of odd degree 3 — never Eulerian. Don’t get fooled by the symmetry.

WE 3

Two odd vertices — case ②

A small network has vertices { A, B, C, D, E } and weighted edges AB(3), BC(5), CD(2), DE(4), AE(6), BD(7). Find the shortest closed route that walks along every edge at least once.

degrees deg(A) = 2 (AB, AE) — even deg(B) = 3 (AB, BC, BD) — odd deg(C) = 2 (BC, CD) — even deg(D) = 3 (CD, DE, BD) — odd deg(E) = 2 (DE, AE) — even odd vertices: B, D → case ② shortest path from B to D direct: BD = 7 via C: BC + CD = 5 + 2 = 7 tied at 7; either works total graph weight 3 + 5 + 2 + 4 + 6 + 7 = 27 CPP route total = 27 + 7 = 34 shortest closed route = 34 always check the indirect route, not just the direct edge — sometimes “BC + CD” beats “BD” by a clear margin.

WE 4

Four odd vertices — three pairings

A graph G has 6 vertices and total edge weight 65. Vertices P, Q, R, S are all of odd degree; the rest are even. The shortest paths between odd vertices are PQ = 12, PR = 8, PS = 14, QR = 10, QS = 6, RS = 9. Find the shortest closed postman route.

4 odd vertices → case ③ three possible pairings PQ + RS = 12 + 9 = 21 PR + QS = 8 + 6 = 14 ★ PS + QR = 14 + 10 = 24 smallest pairing total = 14 CPP route total = 65 + 14 = 79 shortest closed route = 79; pair P with R and Q with S always compute all three pairings — the smallest is often surprising and can be far cheaper than the others.

WE 5

Real-world — road inspector

A road inspector starts and ends at the depot H. The roads (in km) are: HA(6), HB(4), AB(5), AC(3), BC(7), BD(2), CD(8). Find the minimum distance the inspector must walk to check every road.

degrees deg(H) = 2 (HA, HB) — even deg(A) = 3 (HA, AB, AC) — odd deg(B) = 4 (HB, AB, BC, BD) — even deg(C) = 3 (AC, BC, CD) — odd deg(D) = 2 (BD, CD) — even odd vertices: A, C → case ② shortest path from A to C direct: AC = 3 ✓ via B: AB + BC = 5 + 7 = 12 d(A, C) = 3 total graph weight 6 + 4 + 5 + 3 + 7 + 2 + 8 = 35 CPP route total = 35 + 3 = 38 km minimum walking distance = 38 km edge AC = 3 is the direct shortcut between the two odd vertices — perfect for repeating.

WE 6

Open variant — different start and end

Using the same road network as WE 5, suppose the inspector may start at one vertex and finish at any other (not necessarily the depot). Find the new minimum walking distance and state where to start and end.

odd vertices (same as before): A and C open variant with 2 odd vertices start at one odd vertex, end at the other no edge repetition needed route weight total = weight(G) = 35 km minimum distance = 35 km (start at A, end at C, or vice versa) the open variant saves 3 km — exactly the length of the AC repeat we needed in WE 5.

💡 Top tips

Always start with degrees: the number of odd vertices decides which case (0, 2, or 4) applies. Write them out — it’s where method marks live.
The count of odd vertices is always even (Handshaking Lemma). If you count 1, 3, or 5, recount.
Look for direct edges between odd vertices: the shortest path is often that direct edge — but check for cheaper indirect routes too.
For 4 odd vertices, compute all 3 pairings: don’t stop at “small enough” — the optimal can be surprising.
Open variant with 2 odd vertices: the extra freedom completely removes the need for repeats — saves you the shortest path distance.

⚠ Common mistakes

Assuming the direct edge is the shortest path: a chain of cheaper edges (e.g. BC + CD) can beat the direct one (BD). Always compare.
Only trying one or two of the three pairings for the 4-odd case — you must check all three to be sure.
Confusing postman with salesman: postman = every edge at least once; salesman = every vertex exactly once. Different problems entirely.
Forgetting to add the repeat to the graph total: the answer is weight(G) + repeats, not just one or the other.
Not noticing the open variant: if the question says “start and end may differ”, check whether the 2-odd case applies — you might save the shortest-path distance entirely.

Next up — The Travelling Salesman Problem. The postman walks every edge; the salesman visits every vertex. They sound similar but the problems are very different: the salesman version is much harder, and there’s no known clean algorithm to solve it exactly for large graphs. You’ll learn how to use upper- and lower-bound techniques (nearest neighbour and deleted vertex) to sandwich the true answer.

Need help with Graph Theory?

Get 1-on-1 help from an IB examiner who knows exactly what Paper 1 & 2 are looking for.

Book Free Session →