Mathematics Standard • Year 12 • Module 5 • Lesson 5
Hamiltonian Paths and Cycles — Skill Drill
Build fluency in finding Hamiltonian paths and cycles by inspection, distinguishing them from Eulerian routes, and applying Dirac's theorem.
1. Quick recall
Answer each question in the space provided. 1 mark each
Q1.1 Complete the definitions:
A Hamiltonian path visits every __________ exactly once.
A Hamiltonian cycle is a __________ path (starts and ends at the same vertex).
Q1.2 State the key difference between Eulerian and Hamiltonian:
Eulerian uses every __________ once; Hamiltonian visits every __________ once.
Q1.3 Dirac's theorem: in a network with n ≥ 3 vertices, if every vertex has degree at least __________, then a Hamiltonian cycle exists.
2. Worked example — find a Hamiltonian cycle
Problem. Network: pentagon ABCDE with edges AB, BC, CD, DE, EA, AC, BD. Find a Hamiltonian cycle and check whether Dirac's theorem applies.
Step 1 — Try the pentagon edges first.
A–B–C–D–E–A uses AB, BC, CD, DE, EA. All five edges exist ✓.
Step 2 — Verify each vertex visited once.
A, B, C, D, E each appear once before returning to A ✓.
Step 3 — Check Dirac's theorem.
n = 5, n/2 = 2.5. Degrees: deg(A) = 3, deg(B) = 3, deg(C) = 3, deg(D) = 3, deg(E) = 2.
deg(E) = 2 < 2.5 ⇒ Dirac does NOT guarantee a cycle.
Step 4 — But we still found a cycle by inspection.
Dirac is sufficient, not necessary — failing Dirac doesn't mean no cycle exists.
Conclusion. Hamiltonian cycle: A–B–C–D–E–A. Dirac's theorem does not apply (deg(E) < n/2), but a Hamiltonian cycle exists anyway.
3. Faded example — find a Hamiltonian path
Network: A, B, C, D with edges AB, AC, BC, BD. Find a Hamiltonian path. 4 marks
Step 1 — Look at degrees: deg(A) = ____, deg(B) = ____, deg(C) = ____, deg(D) = ____.
Step 2 — Vertex D has degree 1. Therefore any Hamiltonian path must start or end at D.
Step 3 — Try starting from D: D → ______ → ______ → ______ (a path of 4 vertices).
Step 4 — Verify: Are all 4 vertices visited exactly once? ____. Do all edges in the route exist? ____.
Conclusion. A valid Hamiltonian path: ___________________.
4. Graduated practice — find or explain
Foundation — single-step facts (4 questions)
| Q | Problem | Answer |
|---|---|---|
| 4.1 1 | Does the square ABCD (edges AB, BC, CD, DA) have a Hamiltonian cycle? | |
| 4.2 1 | Does K₄ have a Hamiltonian cycle? | |
| 4.3 1 | State whether a Hamiltonian path requires every edge to be used. | |
| 4.4 1 | State the smallest n for which Dirac's theorem applies. |
Standard — typical HSC difficulty (6 questions)
4.5 Find a Hamiltonian cycle in K₅ (the complete graph on 5 vertices A, B, C, D, E). 2 marks
4.6 Network: A–B–C–D (a path on 4 vertices). (a) Find a Hamiltonian path. (b) Does it have a Hamiltonian cycle? Explain. 2 marks
4.7 A network has 6 vertices, each of degree 3. Use Dirac's theorem to decide whether a Hamiltonian cycle is guaranteed to exist. 2 marks
4.8 Star network: centre O connected to A, B, C, D (4 outer vertices, no other edges). (a) Find a Hamiltonian path. (b) Does it have a Hamiltonian cycle? Explain in one sentence. 2 marks
4.9 Network: triangle ABC plus vertex D connected only to A. Find a Hamiltonian path. Is there a Hamiltonian cycle? 2 marks
4.10 Hexagon ABCDEF (a 6-cycle). (a) Find a Hamiltonian cycle. (b) Does Dirac's theorem guarantee one? 2 marks
Extension — find or argue (2 questions)
4.11 Network: K₄ on A, B, C, D plus a vertex E connected only to A. (a) Find a Hamiltonian path. (b) Find a Hamiltonian cycle, or prove none exists. 3 marks
4.12 A round trip for a delivery driver must visit 6 customers in suburbs S₁…S₆ and return to the depot. The road network has edges S₁S₂, S₁S₃, S₂S₃, S₂S₄, S₃S₄, S₃S₅, S₄S₅, S₄S₆, S₅S₆. Find a Hamiltonian cycle (or prove none exists). 3 marks
5. Self-check the easy 3
Tick the first three once you've checked your method works.
How did this worksheet feel?
What I'll revisit before next class:
Q1.1 — Definitions
Hamiltonian path: visits every vertex exactly once. Hamiltonian cycle: a closed Hamiltonian path (start = end).
Q1.2 — Key difference
Eulerian uses every edge once. Hamiltonian visits every vertex once.
Q1.3 — Dirac's theorem
If every vertex has degree at least n / 2, then a Hamiltonian cycle exists.
Q3 — Faded example (edges AB, AC, BC, BD)
Step 1: deg(A) = 2; deg(B) = 3; deg(C) = 2; deg(D) = 1.
Step 2: D has degree 1, so D must be an endpoint.
Step 3: D → B → C → A, OR D → B → A → C. Both work.
Step 4: All 4 vertices visited once ✓. Edges DB, BC, CA (or DB, BA, AC) all exist ✓.
Conclusion: A valid Hamiltonian path: D–B–C–A (or D–B–A–C).
Q4.1 — Square ABCD
Yes — A–B–C–D–A uses AB, BC, CD, DA (all 4 edges) and visits every vertex once.
Q4.2 — K₄
Yes — every pair of vertices is connected, so any ordering is a cycle, e.g. A–B–C–D–A.
Q4.3 — Hamiltonian uses every edge?
No. A Hamiltonian path/cycle visits every vertex, but may skip some edges.
Q4.4 — Smallest n for Dirac
n = 3 (Dirac's theorem requires n ≥ 3).
Q4.5 — Hamiltonian cycle in K₅
Any ordering works (K₅ is complete). Example: A–B–C–D–E–A.
Q4.6 — Path A–B–C–D
(a) Hamiltonian path: A–B–C–D itself. (b) No Hamiltonian cycle — D and A are not connected (no edge AD), so the path cannot close into a cycle.
Q4.7 — Dirac on 6 vertices, all degree 3
n = 6, n/2 = 3. Every vertex has degree 3 ≥ 3. Yes — Dirac guarantees a Hamiltonian cycle.
Q4.8 — Star with 4 outer vertices
(a) A Hamiltonian path would need to visit O once. From one outer vertex, the only edge goes back to O, and from O we go to another outer vertex — but then we are stuck because the only edge from that outer vertex goes back to O (which we have already visited). So the path can have at most 3 vertices (outer–O–outer). No Hamiltonian path exists (4 outer vertices have degree 1; only 2 of them can be endpoints, so the rest cannot be visited).
(b) No Hamiltonian cycle for the same reason: too many degree-1 vertices.
Q4.9 — Triangle ABC + pendant D on A
Hamiltonian path: D–A–B–C (or D–A–C–B). No Hamiltonian cycle — D has degree 1, so it must be an endpoint of any path; a cycle requires every vertex to have an "in" and "out" edge.
Q4.10 — Hexagon ABCDEF
(a) Hamiltonian cycle: A–B–C–D–E–F–A.
(b) n = 6, n/2 = 3. Every vertex has degree 2 < 3 ⇒ Dirac does NOT guarantee a cycle, but one exists anyway (Dirac is sufficient, not necessary).
Q4.11 — K₄ on ABCD with E pendant on A
(a) Hamiltonian path: E–A–B–C–D (or E–A–B–D–C, etc.).
(b) No Hamiltonian cycle — E has degree 1, so it must be an endpoint of any path; no cycle can pass through a degree-1 vertex.
Q4.12 — 6-stop delivery network
Try S₁–S₂–S₄–S₆–S₅–S₃–S₁. Edges used: S₁S₂ ✓, S₂S₄ ✓, S₄S₆ ✓, S₆S₅ ✓, S₅S₃ ✓, S₃S₁ ✓. All edges exist; every vertex visited once before returning to S₁. Hamiltonian cycle exists.