Identifying a Hamiltonian Cycle
What are Hamiltonian paths and cycles?
- A Hamiltonian path is a path in which each vertex in a graph is visited exactly once
- A Hamiltonian cycle is a cycle which visits each vertex in a graph exactly once and returns to its start vertex
- If a graph contains a Hamiltonian cycle then it is known as a Hamiltonian graph
- A graph is semi-Hamiltonian if it contains a Hamiltonian path but not a Hamiltonian cycle
- The only way to show that a graph is Hamiltonian or semi-Hamiltonian is to identify a Hamiltonian cycle or Hamiltonian path
Examiner Tip
- If you are given an adjacency matrix and are asked to find a Hamiltonian cycle, make sure that you sketch out the graph first
Worked example
Let G be the graph shown below.
Show that G is a Hamiltonian graph.
To show that the graph is Hamiltonian, identify a Hamiltonian cycle
ABCFDEA is a Hamiltonian cycle, therefore G is a Hamiltonian graph
There is more than one possible correct Hamiltonian cycle in this graph
