Mathematics Standard • Year 12 • Module 5 • Lesson 4
Eulerian Trails and Circuits — Problem Set
Apply the Eulerian tests to realistic Australian scenarios: garbage collection, postal rounds, bushwalking and council street cleaning.
Problem 1 — Postal round in Newtown
A postal worker must walk every street in a small Newtown block and return to the post office. The street network has 5 intersections A, B, C, D, E with edges (streets): AB, AC, BC, BD, CD, CE, DE.
Set up: What are we solving for?
(i) Compute the degree of each intersection. 1 mark
(ii) Decide whether an Eulerian circuit (which would let the postie return to the post office without retracing a street) exists. Justify with the degree test. 2 marks
(iii) Does an Eulerian trail exist? If yes, identify the two intersections at which the postie must start and end. 2 marks
Stuck? Revisit lesson § Key Ideas — for an Eulerian trail, the two odd-degree vertices are the only valid start/end points.Problem 2 — Garbage truck on a council loop
A council garbage truck must drive every street in a quiet suburban estate and return to the depot. The street layout has 6 corners W, X, Y, Z, P, Q with streets: W–X, X–Y, Y–Z, Z–W (outer square), W–P, X–P, Y–Q, Z–Q (extra spurs).
Set up: What are we solving for?
(i) Compute the degree of every corner. 2 marks
(ii) Decide whether the garbage truck can drive every street exactly once and return to the depot (an Eulerian circuit). Justify. 2 marks
(iii) If a circuit is not possible, identify the minimum number of streets that must be driven twice. (Hint: pair up odd vertices.) 2 marks
Stuck? Each pair of odd-degree vertices contributes 1 retraced edge to the minimum.Problem 3 — Sydney bridges (Königsberg-style)
A tourist visits 4 landmarks linked by 7 footbridges in a fictional layout: North (N), South (S), East (E), West (W). Footbridges: N–W, N–E (two parallel bridges), S–W (two parallel bridges), S–E, W–E. (Note: "two parallel bridges" means two separate edges between the same pair of vertices.)
Set up: What are we solving for?
(i) Compute the degree of each landmark (count each parallel bridge separately). 2 marks
(ii) Can the tourist walk over every bridge exactly once and return to the start? Justify. 2 marks
(iii) Can the tourist walk over every bridge exactly once without needing to return to the start? If yes, state at which landmarks they must begin and end. 2 marks
Stuck? Total bridges = 7; total degree sum should = 14. Use this to verify your counts.Problem 4 — Bushwalking trails in Royal National Park
The park has 5 trails connecting 5 attractions: Wattamolla (W), Garie (G), Bundeena (B), Marley (M), Curracurrong (C). Trails: W–G, W–M, G–B, G–M, B–C, M–C.
Set up: What are we solving for?
(i) Compute the degree of each attraction. 2 marks
(ii) Can a hiker walk every trail exactly once and end at the same attraction they started from? If yes, identify the attraction; if no, explain why. 2 marks
(iii) If a hiker is willing to start and end at different attractions, can they still walk every trail exactly once? Provide one such trail in full. 2 marks
Stuck? Once you have identified the odd-degree vertices, start at one and try to make a trail to the other while exhausting every edge.Problem 5 — Street-cleaning truck in a CBD
A small CBD has 6 intersections I₁…I₆ with two-way streets: I₁–I₂, I₁–I₃, I₂–I₃, I₂–I₄, I₃–I₄, I₃–I₅, I₄–I₅, I₄–I₆, I₅–I₆. The street-cleaning truck must clean every street.
Set up: What are we solving for?
(i) Compute the degree of every intersection and identify the odd ones. 2 marks
(ii) Can the truck clean every street exactly once and return to its starting intersection? Justify with the degree test. 1 mark
(iii) The depot is at I₁ and the truck driver insists on starting there. If an Eulerian circuit is not possible from I₁, what is the minimum extra distance (number of repeated streets) the truck must drive to clean every street and return to I₁? Justify in a brief calculation. 3 marks
Stuck? If there are 2k odd-degree vertices, the minimum repeated edges in a "Chinese-postman" style walk that returns to start is k (pair them up and add a duplicate edge along a shortest path between each pair).How did this worksheet feel?
What I'll revisit before next class:
Problem 1 — Newtown postal round
Set up. We compute degrees, test for Eulerian circuit, then test for Eulerian trail.
(i) Edges: AB, AC, BC, BD, CD, CE, DE. deg(A) = 2; deg(B) = 3; deg(C) = 4; deg(D) = 3; deg(E) = 2. (Sum = 14 = 2 × 7 ✓.)
(ii) Odd vertices: B and D (two of them). NOT all even ⇒ no Eulerian circuit.
(iii) Exactly 2 odd vertices ⇒ Eulerian trail exists. The postie must start at B and end at D (or vice versa).
Problem 2 — Garbage truck
Set up. We compute degrees, test for circuit, then count odd vertices to find the minimum number of streets the truck must drive twice.
(i) Edges: W–X, X–Y, Y–Z, Z–W, W–P, X–P, Y–Q, Z–Q (8 edges). Degrees: deg(W) = 3 (X, Z, P); deg(X) = 3 (W, Y, P); deg(Y) = 3 (X, Z, Q); deg(Z) = 3 (Y, W, Q); deg(P) = 2 (W, X); deg(Q) = 2 (Y, Z). (Sum = 16 = 2 × 8 ✓.)
(ii) Four odd vertices (W, X, Y, Z) ⇒ no Eulerian circuit.
(iii) 4 odd vertices form 2 pairs. To make a circuit, each pair must be "patched" by duplicating one edge between them. Minimum duplicate edges = 2. The truck must drive at least 2 streets twice.
Problem 3 — Sydney bridges
Set up. We count degrees with parallel bridges, then test for circuit and trail.
(i) Bridges: N–W (×1), N–E (×2), S–W (×2), S–E (×1), W–E (×1). Total = 7 bridges.
deg(N) = 1 + 2 = 3.
deg(S) = 2 + 1 = 3.
deg(W) = 1 + 2 + 1 = 4.
deg(E) = 2 + 1 + 1 = 4. (Sum = 3+3+4+4 = 14 = 2 × 7 ✓.)
(ii) Two odd vertices (N and S) ⇒ no Eulerian circuit (would need all even). The tourist cannot end where they started without retracing a bridge.
(iii) Yes — exactly 2 odd vertices ⇒ Eulerian trail exists. The tourist must begin at one of N, S and end at the other.
Problem 4 — Royal NP bushwalk
Set up. Compute degrees, test for circuit, then construct a trail.
(i) Edges: W–G, W–M, G–B, G–M, B–C, M–C. deg(W) = 2 (G, M); deg(G) = 3 (W, B, M); deg(B) = 2 (G, C); deg(M) = 3 (W, G, C); deg(C) = 2 (B, M). (Sum = 12 = 2 × 6 ✓.)
(ii) Odd vertices: G and M. NOT all even ⇒ no Eulerian circuit. The hiker cannot finish at the start without retracing a trail.
(iii) Exactly 2 odd vertices ⇒ Eulerian trail exists; start at G, end at M (or vice versa). One full trail: G–B–C–M–G–W–M. Edges used: G–B, B–C, C–M, M–G, G–W, W–M ✓ (all 6 trails, none repeated).
Problem 5 — CBD street cleaning
Set up. Compute degrees, test for circuit, then apply Chinese-postman pairing for the extra distance.
(i) Edges (9): I₁I₂, I₁I₃, I₂I₃, I₂I₄, I₃I₄, I₃I₅, I₄I₅, I₄I₆, I₅I₆. Degrees: deg(I₁) = 2; deg(I₂) = 3; deg(I₃) = 4; deg(I₄) = 4; deg(I₅) = 3; deg(I₆) = 2. (Sum = 18 = 2 × 9 ✓.) Odd vertices: I₂ and I₅.
(ii) Two odd vertices ⇒ no Eulerian circuit (would need 0 odd). An open Eulerian trail exists from I₂ to I₅.
(iii) To return to I₁, the truck must add a duplicate path between the two odd vertices I₂ and I₅. Shortest path I₂ → I₅ uses 2 edges (e.g. I₂–I₃–I₅). So the truck must drive at least 2 extra streets (duplicate edges along the I₂–I₃–I₅ pair), giving a total of 11 street traversals to clean all 9 streets and return to I₁.