Hamiltonian Graphs (Edexcel International AS Maths) : Revision Note
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 Tips and Tricks
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
You've read 0 of your 5 free revision notes this week
Sign up now. It’s free!
Did this page help you?