Mathematics Standard • Year 12 • Module 5 • Lesson 5
Hamiltonian Paths and Cycles — Problem Set
Apply the Hamiltonian toolkit to realistic Australian scenarios: travelling salesperson, tourist itinerary, sports venue tours and delivery routes.
Problem 1 — Delivery driver visiting 5 customers
An online retailer's driver must visit 5 customers C₁…C₅ in suburban Adelaide and return to the depot at C₁. The road network has direct roads: C₁–C₂, C₁–C₃, C₂–C₃, C₂–C₄, C₃–C₄, C₃–C₅, C₄–C₅.
Set up: What are we solving for?
(i) Find a Hamiltonian cycle starting and ending at C₁. 2 marks
(ii) The driver claims there is more than one Hamiltonian cycle from C₁. Find a second cycle. 1 mark
(iii) A new edge C₁–C₅ is added. Does this enable any new Hamiltonian cycles? If yes, give one; if no, explain. 2 marks
Stuck? Revisit lesson § Card 02 — start from a low-degree vertex (e.g., C₅) and work outward.Problem 2 — Tasmanian east-coast itinerary
A tourist wants to visit each of 6 attractions exactly once: Launceston (L), St Helens (S), Bicheno (B), Freycinet (F), Coles Bay (C), Hobart (H). Direct sealed-road links are: L–S, L–B, S–B, S–F, B–F, B–C, F–C, F–H, C–H.
Set up: What are we solving for?
(i) Find a Hamiltonian path from Launceston to Hobart. 2 marks
(ii) Find a Hamiltonian cycle (start = end at Launceston). If none exists, justify. 2 marks
(iii) Apply Dirac's theorem (n = 6, n/2 = 3). Identify which attractions, if any, have degree below n/2. State whether Dirac guarantees a Hamiltonian cycle here. 2 marks
Stuck? Dirac is sufficient (not necessary). Failing Dirac does not rule out a Hamiltonian cycle.Problem 3 — AFL grand-final venue tour
A media crew visits 5 facilities at the MCG on grand-final day: Members Stand (M), Broadcast Booth (B), Player Tunnel (P), Coach Box (C), Ground Centre (G). Walkways exist between: M–B, M–P, B–C, B–G, C–G, P–G.
Set up: What are we solving for?
(i) Find a Hamiltonian path that starts at M. 2 marks
(ii) Find a Hamiltonian cycle that starts and ends at M. 2 marks
(iii) The producer says, "We need to visit B last." Find a Hamiltonian path from M to B that visits every facility exactly once. 2 marks
Stuck? Map out P's neighbours (only M and G), so the path must enter or leave P via one of those two.Problem 4 — Eulerian vs Hamiltonian (showroom layout)
A car dealership in Geelong has 6 display zones D₁…D₆ connected by aisles: D₁–D₂, D₁–D₃, D₂–D₃, D₂–D₄, D₃–D₄, D₃–D₅, D₄–D₅, D₄–D₆, D₅–D₆.
Set up: What are we solving for?
(i) The cleaner needs to walk every aisle exactly once. (a) Find the degree of each zone. (b) Decide whether an Eulerian circuit, Eulerian trail, or neither is possible. 2 marks
(ii) The customer service walker needs to visit every zone exactly once and return to the entrance D₁. Find a Hamiltonian cycle. 2 marks
(iii) Write a one-sentence explanation distinguishing what the cleaner is looking for (Eulerian) from what the walker is looking for (Hamiltonian). 1 mark
Stuck on (ii)? Try D₁–D₂–D₄–D₆–D₅–D₃–D₁ and verify each edge exists.Problem 5 — Star-shaped tour (impossibility check)
A regional museum has a central foyer (F) and 5 satellite galleries G₁…G₅. The only connections are F–G₁, F–G₂, F–G₃, F–G₄, F–G₅ (i.e., it is a star with F at the centre).
Set up: What are we solving for?
(i) Compute the degree of each vertex. 1 mark
(ii) Decide whether a Hamiltonian path exists. Justify rigorously using the "degree-1 vertex must be an endpoint" rule. 3 marks
(iii) A donor offers to fund an additional walkway. State the minimum number of new walkways required so that a Hamiltonian path (visiting every gallery exactly once) becomes possible, and justify briefly. 2 marks
Stuck on (ii)? In a star with k outer vertices, only 2 outer vertices can be endpoints of a Hamiltonian path — the other (k − 2) outer vertices have degree 1 each and can never be "passed through".How did this worksheet feel?
What I'll revisit before next class:
Problem 1 — Adelaide delivery
Set up. We find a Hamiltonian cycle starting at C₁, then look for a second cycle, then check what changes when C₁–C₅ is added.
(i) Try C₁–C₂–C₄–C₅–C₃–C₁. Edges: C₁C₂ ✓, C₂C₄ ✓, C₄C₅ ✓, C₅C₃ ✓, C₃C₁ ✓. All 5 vertices visited once ⇒ valid Hamiltonian cycle.
(ii) Another: C₁–C₃–C₅–C₄–C₂–C₁. (This is the reverse — markers should accept it as a "different cycle" only if listed separately, OR accept a genuinely different second cycle. A second example: C₁–C₂–C₃–C₅–C₄–? C₄ → C₁? No edge C₄C₁. So this routing fails. The "reverse" is the only natural second cycle.)
(iii) With new edge C₁–C₅: new cycle C₁–C₅–C₃–C₂–C₄–? need C₄–C₁ which still doesn't exist. Try C₁–C₅–C₄–C₂–C₃–C₁. Edges: C₁C₅ (new ✓), C₅C₄ ✓, C₄C₂ ✓, C₂C₃ ✓, C₃C₁ ✓. Yes — new cycle made possible by the C₁–C₅ edge.
Problem 2 — Tasmanian east coast
Set up. We find a Hamiltonian path L → H, then test for a cycle, then apply Dirac.
(i) One Hamiltonian path: L–S–B–C–F–H. Edges: LS ✓, SB ✓, BC ✓, CF ✓, FH ✓. All 6 attractions visited once ⇒ valid Hamiltonian path.
(ii) Try L–S–F–H–C–B–L. Edges: LS ✓, SF ✓, FH ✓, HC ✓, CB ✓, BL ✓. All 6 visited once and returns to L ⇒ Hamiltonian cycle exists.
(iii) Degrees: deg(L) = 2 (S, B); deg(S) = 3; deg(B) = 4; deg(F) = 4; deg(C) = 3; deg(H) = 2. n/2 = 3. Below n/2: L and H both have degree 2 < 3. Dirac does NOT guarantee a cycle in this network — but one exists anyway (as we found in (ii)).
Problem 3 — MCG facility tour
Set up. Hamiltonian path from M, then cycle from M, then constrained path M → B.
(i) One Hamiltonian path from M: M–P–G–C–B. Edges: MP ✓, PG ✓, GC ✓, CB ✓. All 5 visited once.
(ii) Hamiltonian cycle: M–P–G–C–B–M. Edges: MP ✓, PG ✓, GC ✓, CB ✓, BM ✓. ✓ All 5 visited once and returns to M.
(iii) M to B visiting all: M–P–G–C–B (same path as (i)). All facilities visited, B is last.
Problem 4 — Geelong showroom
Set up. Eulerian check for the cleaner; Hamiltonian cycle for the walker; one-sentence distinction.
(i) Edges (9): D₁D₂, D₁D₃, D₂D₃, D₂D₄, D₃D₄, D₃D₅, D₄D₅, D₄D₆, D₅D₆. Degrees: deg(D₁) = 2; deg(D₂) = 3; deg(D₃) = 4; deg(D₄) = 4; deg(D₅) = 3; deg(D₆) = 2. Two odd vertices (D₂, D₅) ⇒ Eulerian trail exists (not a circuit).
(ii) Try D₁–D₂–D₄–D₆–D₅–D₃–D₁. Edges: D₁D₂ ✓, D₂D₄ ✓, D₄D₆ ✓, D₆D₅ ✓, D₅D₃ ✓, D₃D₁ ✓. ✓ Hamiltonian cycle.
(iii) Eulerian routes are about using every edge exactly once (the cleaner needs every aisle); Hamiltonian routes are about visiting every vertex exactly once (the walker needs every zone).
Problem 5 — Star museum
Set up. Degrees, impossibility argument for the Hamiltonian path, then minimal new edges to fix.
(i) deg(F) = 5; each gallery deg = 1 (only one walkway, the spoke to F).
(ii) Five galleries each have degree 1. In any path, every internal (non-endpoint) vertex must have degree at least 2 — you must enter and leave. So a degree-1 vertex can ONLY appear at an end. A Hamiltonian path has only 2 endpoints, but we have 5 degree-1 vertices ⇒ impossible. Most galleries cannot be visited without revisiting F.
(iii) To make a Hamiltonian path possible, at most 2 vertices can have degree 1. We must raise 3 of the 5 galleries' degrees from 1 to ≥ 2. Each new walkway raises the degree of 2 vertices by 1. So at minimum we need walkways connecting the "interior" galleries pairwise — e.g. G₁–G₂, G₂–G₃, G₃–G₄ (a chain). 3 new walkways suffice (G₁–G₂, G₂–G₃, G₃–G₄ leaves G₄ degree 2 and G₅ degree 1; a path G₅–F–G₁–G₂–G₃–G₄ visits all 6). Minimum: 3 new walkways. (Markers should accept any reasoning that achieves ≤ 2 degree-1 vertices with at most 3 new edges.)