Mathematics Standard • Year 12 • Module 5 • Lesson 4
Eulerian Trails and Circuits — Past-Paper Style
Practise HSC Mathematics Standard 2 short-answer and extended-response writing on Eulerian circuits and trails.
1. Short-answer questions
1.1 A connected network has degree sequence 2, 4, 4, 4, 4. Does the network have an Eulerian circuit, an Eulerian trail, or neither? Justify your answer using the degree test. 2 marks Band 3
1.2 A connected network has 6 vertices with degrees 2, 2, 3, 3, 4, 4.
(a) State whether it has an Eulerian circuit.
(b) State whether it has an Eulerian trail. If yes, identify the only valid start/end vertices (by degree). 3 marks Band 3-4
1.3 The diagram shows a small Penrith council park map: 5 garden zones G₁…G₅ connected by paths G₁G₂, G₁G₃, G₂G₃, G₂G₄, G₃G₄, G₃G₅, G₄G₅.
(a) Find the degree of each garden zone.
(b) Decide whether a gardener can walk every path exactly once and return to the start (an Eulerian circuit). Justify.
(c) If not, identify the two zones the gardener must start and finish at to walk every path exactly once without retracing. 4 marks Band 4
2. Extended response
2.1 A Bondi Beach council services 6 stretches of footpath connecting 5 main viewing platforms P₁…P₅. The footpath network has the following edges:
P₁–P₂, P₁–P₃, P₂–P₃, P₂–P₄, P₃–P₄, P₃–P₅, P₄–P₅.
(a) Compute the degree of each platform and identify all odd-degree platforms.
(b) Determine whether a single street-cleaner can clean every footpath exactly once. If a circuit is possible, find one; if only a trail is possible, find one and state where it starts and ends.
(c) The council decides to add ONE new footpath to make a full Eulerian circuit possible. Identify which single new footpath (if any) would do this, and write a one-sentence conclusion explaining the change in degrees. 7 marks Band 5-6
Explicit marking criteria
Part (a) — 2 marks
• 1 mark — all 5 degrees correct.
• 1 mark — odd-degree vertices identified.
Part (b) — 3 marks
• 1 mark — correctly states no Eulerian circuit (4 odd vertices), or that a trail is possible with only 2 odd.
• 1 mark — finds a valid trail (or proves impossibility).
• 1 mark — names start and end of the trail explicitly.
Part (c) — 2 marks
• 1 mark — identifies a single footpath that, when added, makes all degrees even (or proves no single edge suffices).
• 1 mark — explicit conclusion sentence about parity of degrees.
Your response:
Stuck on (c)? Adding one edge flips the parity of TWO vertices (the two it joins). So one new edge can fix at most 2 odd vertices.How did this worksheet feel?
What I'll revisit before next class:
1.1 — Degree sequence 2, 4, 4, 4, 4 (2 marks)
Sample response.
All degrees are even (2, 4, 4, 4, 4). The network is connected. Therefore the network has an Eulerian circuit (every vertex even).
Marking notes. 1 mark — states "all even" correctly. 1 mark — names "Eulerian circuit" with justification. A bare "circuit" without justification scores 1/2.
1.2 — Degree sequence 2, 2, 3, 3, 4, 4 (3 marks)
Sample response.
(a) Odd vertices: the two degree-3 vertices. Not all even ⇒ no Eulerian circuit.
(b) Exactly 2 odd ⇒ Eulerian trail exists. The only valid start/end pair is the two degree-3 vertices.
Marking notes. 1 mark — recognises 2 odd. 1 mark — no circuit. 1 mark — trail exists and identifies the degree-3 vertices as the start/end.
1.3 — Penrith park (4 marks)
Sample response.
(a) Edges: G₁G₂, G₁G₃, G₂G₃, G₂G₄, G₃G₄, G₃G₅, G₄G₅. deg(G₁) = 2; deg(G₂) = 3; deg(G₃) = 4; deg(G₄) = 3; deg(G₅) = 2.
(b) Odd vertices: G₂ and G₄ (two of them). Not all even ⇒ no Eulerian circuit. The gardener cannot finish at the starting garden without retracing a path.
(c) Two odd vertices ⇒ Eulerian trail exists; the gardener must start at G₂ and finish at G₄ (or vice versa).
Marking notes. (a) 1 mark — all 5 degrees correct. (b) 1 mark — no circuit; 1 mark — justification with degree test. (c) 1 mark — names G₂ and G₄ explicitly.
2.1 — Bondi footpaths (7 marks): sample Band-6 response
Sample Band-6 response.
(a) Degrees and odd vertices.
Edges (7 in total): P₁P₂, P₁P₃, P₂P₃, P₂P₄, P₃P₄, P₃P₅, P₄P₅.
deg(P₁) = 2 (P₂, P₃); deg(P₂) = 3 (P₁, P₃, P₄); deg(P₃) = 4 (P₁, P₂, P₄, P₅); deg(P₄) = 3 (P₂, P₃, P₅); deg(P₅) = 2 (P₃, P₄).
Check: sum = 14 = 2 × 7 ✓.
Odd-degree platforms: P₂ and P₄. [1 mark — degrees; 1 mark — odd vertices identified.]
(b) Eulerian assessment.
Exactly 2 odd vertices ⇒ no Eulerian circuit, but an Eulerian trail exists. [1 mark — applies test correctly.]
One valid trail: P₂–P₁–P₃–P₂–P₄–P₃–P₅–P₄. Edges used in order: P₂P₁, P₁P₃, P₃P₂, P₂P₄, P₄P₃, P₃P₅, P₅P₄. All 7 edges used, none repeated ✓. [1 mark — valid trail.]
Start at P₂, end at P₄. [1 mark — names start and end.]
(c) One new footpath to enable a circuit.
To enable an Eulerian circuit, every degree must be even. Adding a single new edge changes the parity of its two endpoints. We need to flip exactly the two currently odd vertices (P₂ and P₄). Therefore, the new footpath must be P₂–P₄ (if not already present — and it is NOT). Adding P₂–P₄ raises deg(P₂) to 4 and deg(P₄) to 4, making every vertex even. [1 mark — identifies single edge that fixes both odd vertices.]
Conclusion: adding the footpath P₂–P₄ converts both odd-degree platforms to even degree, making every platform's degree even and so enabling an Eulerian circuit on the new network. [1 mark — explicit conclusion about parity.]
Total: 7/7.
Band descriptors for marker.
Band 3: Degrees correct, but identifies wrong odd vertices or fails to test the circuit/trail conditions. ≈ 3 marks.
Band 4: Degrees and odd vertices correct, trail attempted but not completed correctly. ≈ 4-5 marks.
Band 5: All parts complete and a valid trail found, but (c) misses the "single edge fixes parity" insight or names a wrong edge. ≈ 6 marks.
Band 6: Complete, with valid trail, correct new edge P₂–P₄, and explicit parity conclusion. 7/7.