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₁.