The railway lines connecting a city’s tourist attraction are shown below:

Kerry is visiting the city and would like to visit each of the attractions. She is indifferent about how many edges of the graph she traverses.

A Hamiltonian cycle is a cycle which visits each vertex (except the starting and ending vertex) exactly once. A Hamiltonian path is a path which visits each vertex exactly once, but does not start and end at the same vertex.

On the left-hand graph above, A -> B -> C -> D -> E -> F -> A is a Hamiltonian cycle. On the right-hand graph above B -> D -> F -> A -> G -> E -> C is a Hamiltonian path.

A graph is Hamiltonian if it contains a Hamiltonian cycle and semi-Hamiltonian if it contains a Hamiltonian path, but not a Hamiltonian cycle.

Worked Example

• For the graph above:
  • Find a Hamiltonian cycle which starts and ends at A.
  • Find a Hamiltonian path which starts at E and ends at B.

Exercise

Answers