Lesson 8: Hamiltonian paths and cycles
A dead-end road makes a graph semi-Hamiltonian
SkillHamiltonian paths and cycles
Worked example
The graph shows the roads between five places on an island.
(a) Explain why the graph has no Hamiltonian cycle.
(b) Find a Hamiltonian path, and state what kind of graph this is.
Step 1: Look for a vertex of degree 1
The Jetty has degree 1 — only the road from the Beach meets it.
Step 2: Explain why there is no Hamiltonian cycle
A cycle arrives at each vertex along one edge and leaves along a different edge, so every vertex on a cycle needs degree at least 2. A cycle could reach the Jetty but never leave it, so the graph has no Hamiltonian cycle.
The same reasoning shows that a vertex of degree 2 forces both of its edges into any Hamiltonian cycle.
Step 3: Start the path at the Jetty
The Jetty can only be at an end of a Hamiltonian path, so start there and keep going to unvisited places — Jetty–Beach–Town–Farm–Lookout.
Step 4: Check and classify
The path visits all five places exactly once. ✓ The graph has a Hamiltonian path but no Hamiltonian cycle, so it is semi-Hamiltonian.
Answer
(a) The Jetty has degree 1, so a cycle could reach it but never leave it. (b) For example Jetty–Beach–Town–Farm–Lookout. The graph is semi-Hamiltonian.
Try a similar one
A fresh question of the same kind, checked as you answer, with hints and a full solution.
Method
A vertex of degree 1 rules out a Hamiltonian cycle and must be an end of any Hamiltonian path.
Build the path outwards from that vertex, checking each place is visited once.
Watch out for
Thinking every road must be used. A Hamiltonian path visits every place once; the roads Town–Lookout and Beach–Lookout are not needed.