You are viewing a free preview of this lesson.
Subscribe to unlock all 10 lessons in this course and every other course on LearningBro.
A postal worker must walk along every street of a town and return to the depot, covering the least possible total distance. A gritter must salt every road; a street-sweeper must clean every kerb; an inspector must check every pipe. All of these are the route inspection problem — historically the Chinese Postman problem, after the mathematician Mei-Ko Kwan who first studied it. The question is sharp: what is the minimum total weight of a closed walk that traverses every edge of a network at least once? The answer turns entirely on the odd-degree vertices and the handshaking lemma met in Lesson 1, stitched together with Dijkstra's shortest paths from Lesson 4 — a perfect synoptic finale to the network-algorithms strand.
Route inspection is a headline optimisation problem of the Paper 3 Discrete option (7367/3D) (Paper 3: 2 h, 100 marks, 33⅓%; AO1 40% / AO2 25% / AO3 35%). Executing the pairing procedure is AO1; explaining why duplicating the minimum pairing is optimal, and interpreting the answer in context, is AO2/AO3. It is a favourite because it combines earlier tools — degrees (Lesson 1), shortest paths (Lesson 4) — so it tests whether you can assemble a multi-step solution.
A closed walk using every edge exactly once is an Eulerian circuit, and one exists iff the network is connected and every vertex has even degree (Lesson 1). In that lucky case the minimum route weight is simply
minimum route=∑e∈Ew(e),
with no edge repeated. If some vertices have odd degree, an Eulerian circuit is impossible, so some edges must be walked more than once. The art is to repeat the cheapest set of edges that restores all-even degrees — and you only ever need to repeat (duplicate) edges between odd-degree vertices.
By the handshaking lemma the number of odd-degree vertices is even, so they can always be paired up.
minimum route=e∈E∑w(e)+(weight of the minimum odd-vertex pairing).
The number of perfect matchings of 2k odd vertices is the double factorial
(2k−1)!!=(2k−1)(2k−3)⋯3⋅1,
so 2 odd vertices give 1 pairing, 4 give 3, 6 give 15, and 8 give 105.
Network on A, B, C, D, E with edges AB(3), AC(5), BC(2), BD(4), CD(6), DE(3). Find the minimum route-inspection weight (start and finish at the same vertex).
Degrees.
| Vertex | A | B | C | D | E |
|---|---|---|---|---|---|
| Degree | 2 | 3 | 3 | 3 | 1 |
Odd-degree vertices: B, C, D, E (four — an even number ✓). (M1 for identifying the odd vertices.)
Shortest distances between odd vertices (by inspection):
d(B,C)d(C,D)=2,=6,d(B,D)d(C,E)=4,=9 (C−D−E or C−B−D−E),d(B,E)d(D,E)=4+3=7,=3.(A1 for the shortest distances, especially d(C,E)=9 and d(B,E)=7.)
The three pairings of {B,C,D,E}:
| Pairing | Weight |
|---|---|
| (B,C) + (D,E) | 2+3=5 |
| (B,D) + (C,E) | 4+9=13 |
| (B,E) + (C,D) | 7+6=13 |
Minimum pairing: (B,C) + (D,E), weight 5. (M1 list all pairings; A1 select minimum 5.)
Duplicate edges BC(2) and DE(3). Sum of all edges:
∑ew(e)=3+5+2+4+6+3=23.
Minimum route weight:
23+5=28. (A1 for the sum 23; A1 for the final 28.)
graph LR
A((A)) ---|3| B((B))
A ---|5| C((C))
B ---|2| C
B ---|4| D((D))
C ---|6| D
D ---|3| E((E))
Exam tip. List every pairing and its total, even the non-optimal ones — examiners award marks for the complete pairing comparison, and it guards against picking a sub-optimal matching by eye.
Network on A, B, C, D, E, F with edges AB(4), AC(3), BC(2), BD(5), CE(6), DE(4), DF(3), EF(2). Find the minimum route-inspection weight.
Degrees: A=2, B=3, C=3, D=3, E=3, F=2; odd vertices B, C, D, E.
Shortest distances: d(B,C)=2; d(D,E)=4; d(B,D)=5; d(C,E)=6; d(B,E)=B−C−E=2+6=8; d(C,D)=C−B−D=2+5=7.
| Pairing | Weight |
|---|---|
| (B,C) + (D,E) | 2+4=6 |
| (B,D) + (C,E) | 5+6=11 |
| (B,E) + (C,D) | 8+7=15 |
Minimum pairing: (B,C) + (D,E), weight 6. Sum of all edges =4+3+2+5+6+4+3+2=29. Minimum route weight =29+6=35.
graph LR
A((A)) ---|4| B((B))
A ---|3| C((C))
B ---|2| C
B ---|5| D((D))
C ---|6| E((E))
D ---|4| E
D ---|3| F((F))
E ---|2| F
A network on A, B, C, D has edges AB(2), BC(3), CD(4), DA(5), AC(6). (a) Find the minimum closed inspection route (return to start). (b) Find the minimum route if the inspector may finish anywhere.
Degrees: A=3 (AB,DA,AC), B=2, C=3 (BC,CD,AC), D=2. Odd vertices: A and C — exactly two, so there is only one pairing.
(a) Closed route. The single pairing is (A,C); the shortest A–C distance is d(A,C)=5 via A−B−C (2+3), which beats the direct edge AC=6. Duplicate the edges AB and BC. Sum of all edges =2+3+4+5+6=20, so
minimum closed route=20+5=25.
(M1 identify the two odd vertices and the one pairing; A1 d(A,C)=5; A1 final 25.) Crucially we use the path A–B–C, not the direct AC edge — a classic trap.
(b) Open route. If the inspector may start at A and finish at C (the two odd vertices), the augmented duplication is unnecessary: a graph with exactly two odd-degree vertices has an open Eulerian trail between them, traversing every edge exactly once. Hence
minimum open route=∑ew(e)=20,
saving exactly the 5 we would otherwise repeat. This illustrates the general principle: the open route (free finish) is cheaper than the closed route by precisely the smallest pairing we are allowed to leave undone — here the one and only odd pair.
Most AQA questions ask only for the minimum total weight, but you may be asked to state a route. Once the augmented graph is all-even, an Eulerian circuit always exists, and a simple rule builds one: never cross a bridge unless you have no other choice (Fleury's rule). Equivalently, walk any trail until you return to the start, then splice in detours around any edges you have not yet used (Hierholzer's method). In Worked Example 4.1, after duplicating BC and DE the degrees become A=2, B=4, C=4, D=4, E=2 — all even — and one valid closed route is
A→B→C→B→D→C→A, then …
with the duplicated copies of BC and DE walked as the "second pass". You do not need to memorise a route-construction algorithm for full marks on a length question, but being able to write down a valid Eulerian route demonstrates that your duplication genuinely makes the traversal possible — and it is the natural sanity check that your odd-vertex pairing was correct.
Real inspection problems add wrinkles worth knowing. If some streets are one-way, the network is a digraph and the problem becomes the directed Chinese Postman: you balance each vertex so in-degree equals out-degree, solved by minimum-cost flow rather than matching. If only a subset of streets must be covered (e.g. only the main roads need gritting), it becomes the Rural Postman Problem, which is NP-hard. And if the depot differs from the finish, you are in the open-route variant above. Recognising which variant a worded question describes — closed vs open, all edges vs a subset, undirected vs one-way — is itself an AO3 skill, because choosing the wrong model guarantees the wrong answer however flawless the arithmetic.
(Specimen-style — not from any past paper.)
A park's footpaths are modelled by a network on six junctions P, Q, R, S, T, U. The path lengths (metres) are PQ(50), PR(40), QR(30), QS(60), RT(70), ST(20), SU(35), TU(45). The warden must inspect every path and return to P. (a) Show that the network is not Eulerian and identify the odd-degree vertices. [2] (b) The shortest distances between the odd vertices are d(Q,R)=30, d(Q,U)=95, d(R,U)=105, d(Q,R) etc. Determine the minimum total distance the warden must walk. [4]
Model solution. (a) Degrees: P=2,Q=3,R=3,S=3,T=3,U=2. Four vertices (Q, R, S, T) have odd degree, so no Eulerian circuit exists. [M1 A1] (b) Odd vertices Q, R, S, T. Shortest distances: d(Q,R)=30, d(S,T)=20, d(Q,S)=60, d(R,T)=70, d(Q,T)=Q−R−T=100 (or Q−S−T=80, so 80), d(R,S)=R−Q−S=90 (or R−T−S=90, so 90). Pairings: (Q,R)+(S,T)=30+20=50;(Q,S)+(R,T)=60+70=130;(Q,T)+(R,S)=80+90=170. Minimum pairing =50, duplicating QR and ST. Sum of edges =50+40+30+60+70+20+35+45=350. Minimum route =350+50=400 m. [M1 pairings; A1 minimum 50; A1 sum 350; A1 total 400]
Subscribe to continue reading
Get full access to this lesson and all 10 lessons in this course.