Mathematics Standard • Year 12 • Module 5 • Lesson 5
Hamiltonian Paths and Cycles — Past-Paper Style
Practise HSC Mathematics Standard 2 short-answer and extended-response writing on Hamiltonian paths and cycles.
1. Short-answer questions
1.1 A network has vertices A, B, C, D and edges AB, AC, BC, BD, CD. Find a Hamiltonian cycle starting and ending at A. 2 marks Band 3
1.2 A connected network has 7 vertices and the degree of every vertex is at least 4.
(a) Does Dirac's theorem guarantee a Hamiltonian cycle? Justify.
(b) State one Hamiltonian-style example (in words) of a real-world tour problem this network could represent. 3 marks Band 3-4
1.3 A school tour visits 5 classrooms R₁…R₅ connected by corridors: R₁–R₂, R₁–R₃, R₂–R₃, R₂–R₄, R₃–R₄, R₃–R₅, R₄–R₅.
(a) Find a Hamiltonian path from R₁ to R₅.
(b) Find a Hamiltonian cycle starting and ending at R₁ (or prove none exists).
(c) State, in one sentence, the difference between this Hamiltonian-cycle task and an Eulerian-circuit task on the same network. 4 marks Band 4
2. Extended response
2.1 A real-estate agent must drive a tour of 6 properties P₁…P₆ in regional Bathurst with a prospective buyer, starting and finishing at P₁. The available roads form the following network:
P₁–P₂, P₁–P₃, P₂–P₃, P₂–P₄, P₃–P₄, P₃–P₅, P₄–P₅, P₄–P₆, P₅–P₆.
(a) Find a Hamiltonian cycle that visits every property exactly once and returns to P₁.
(b) The agent's buyer prefers to see P₆ second-last (so the route ends "…–P₆–P₁"). Find any Hamiltonian cycle satisfying this preference, or explain why it is impossible.
(c) Compare your work to the agent's original "rough" cycle P₁–P₃–P₅–P₆–P₄–P₂–P₁. Verify whether every edge in the rough cycle exists, and write a one-sentence conclusion about whether the rough cycle is valid and, if so, whether it satisfies the buyer's preference. 7 marks Band 5-6
Explicit marking criteria
Part (a) — 2 marks
• 1 mark — proposes a 6-vertex cycle using only existing edges.
• 1 mark — explicit verification that every edge in the cycle exists.
Part (b) — 2 marks
• 1 mark — recognises that P₁ must have edge to P₆ for the cycle to end "…–P₆–P₁"; checks whether edge P₁P₆ exists.
• 1 mark — provides a working cycle if possible, or a clear impossibility statement.
Part (c) — 3 marks
• 1 mark — checks each of the 6 edges in the proposed rough cycle against the network.
• 1 mark — correctly concludes whether the rough cycle is valid.
• 1 mark — explicit conclusion sentence on (i) validity and (ii) whether buyer's preference is satisfied.
Your response:
Stuck on (b)? "Ends …–P₆–P₁" requires the edge P₆–P₁ to be present. Check the edge list.How did this worksheet feel?
What I'll revisit before next class:
1.1 — Hamiltonian cycle at A (2 marks)
Sample response.
Try A–B–D–C–A. Edges: AB ✓, BD ✓, DC ✓, CA ✓. All 4 vertices visited once and returns to A ⇒ valid Hamiltonian cycle.
Marking notes. 1 mark — valid cycle proposed. 1 mark — explicit verification all edges exist. Alternative cycles: A–C–D–B–A, A–B–C–D–? (need DA — no edge DA in the given list, so this would fail!) — careful, the edges given are AB, AC, BC, BD, CD only; no DA. A–B–D–C–A and A–C–D–B–A are the two valid Hamiltonian cycles.
1.2 — Dirac on 7 vertices, degree ≥ 4 (3 marks)
Sample response.
(a) n = 7, n/2 = 3.5. Every vertex has degree ≥ 4 ≥ 3.5. Yes — Dirac's theorem guarantees a Hamiltonian cycle.
(b) Example: a delivery driver who must visit 7 customers exactly once and return to the depot — the network represents direct roads between any two customers' addresses.
Marking notes. (a) 1 mark — quotes Dirac condition; 1 mark — applies correctly. (b) 1 mark — a sensible "visit every vertex once" tour story (delivery, sales, school inspector, etc.).
1.3 — Classroom corridor network (4 marks)
Sample response.
(a) R₁–R₂–R₄–R₅–R₃ uses R₁R₂, R₂R₄, R₄R₅, R₅R₃. Wait — need to end at R₅. Try R₁–R₃–R₂–R₄–R₅: edges R₁R₃ ✓, R₃R₂ ✓, R₂R₄ ✓, R₄R₅ ✓. All 5 visited once ⇒ valid Hamiltonian path R₁ → R₅.
(b) Cycle R₁ → R₁: try R₁–R₂–R₄–R₅–R₃–R₁. Edges: R₁R₂ ✓, R₂R₄ ✓, R₄R₅ ✓, R₅R₃ ✓, R₃R₁ ✓. ✓ Valid Hamiltonian cycle.
(c) A Hamiltonian cycle visits every classroom exactly once; an Eulerian circuit uses every corridor exactly once. The cycle counts vertices; the circuit counts edges.
Marking notes. (a) 1 mark — valid path. (b) 1 mark — proposes cycle; 1 mark — explicit edge check. (c) 1 mark — "vertices vs edges" distinction in one sentence.
2.1 — Bathurst real-estate tour (7 marks): sample Band-6 response
Sample Band-6 response.
(a) Hamiltonian cycle at P₁.
Try P₁–P₂–P₄–P₆–P₅–P₃–P₁. Edges: P₁P₂ ✓, P₂P₄ ✓, P₄P₆ ✓, P₆P₅ ✓, P₅P₃ ✓, P₃P₁ ✓. All 6 properties visited exactly once and returns to P₁. [1 mark — proposes cycle; 1 mark — edge verification.]
(b) Cycle ending "…–P₆–P₁".
For the cycle to end "…–P₆–P₁", the edge P₆–P₁ must exist. Checking the network: edges containing P₁ are P₁–P₂ and P₁–P₃ only. There is no edge P₁–P₆. Therefore no Hamiltonian cycle can end with the segment "…–P₆–P₁" using only existing roads. The buyer's preference is incompatible with the road network. [1 mark — recognises P₆P₁ requirement; 1 mark — concludes impossibility with justification.]
(c) Verify the rough cycle P₁–P₃–P₅–P₆–P₄–P₂–P₁.
Edge-by-edge check: P₁P₃ ✓, P₃P₅ ✓, P₅P₆ ✓, P₆P₄ ✓, P₄P₂ ✓, P₂P₁ ✓. All 6 edges exist; all 6 properties visited once; returns to P₁ ⇒ the rough cycle is a valid Hamiltonian cycle. [1 mark — edge-by-edge verification; 1 mark — correct validity conclusion.]
However, the cycle ends "…–P₂–P₁", with P₆ visited in the middle (third stop). So it does not satisfy the buyer's preference for P₆ to be second-last.
Conclusion: the rough cycle P₁–P₃–P₅–P₆–P₄–P₂–P₁ is a valid Hamiltonian cycle on the existing road network, but it does not satisfy the buyer's preference for P₆ to be the second-last stop. As shown in part (b), no Hamiltonian cycle can end with P₆–P₁ because the road P₆–P₁ does not exist. [1 mark — explicit conclusion covering both validity and preference.]
Total: 7/7.
Band descriptors for marker.
Band 3: Attempts (a) with an incomplete or invalid cycle; little engagement with (b) or (c). ≈ 3 marks.
Band 4: Valid cycle in (a); recognises issue in (b) but doesn't fully justify; verifies (c) edges only. ≈ 4-5 marks.
Band 5: All numerical parts correct; clear validity statement in (c) but no explicit comment on the buyer's preference. ≈ 6 marks.
Band 6: Complete, with conclusion sentence covering BOTH validity and the buyer-preference dimension. 7/7.