Lesson 8: Hamiltonian paths and cycles

A dead-end road makes a graph semi-Hamiltonian

SkillHamiltonian paths and cycles

Worked example

  • Complex familiar

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.

1 of 4 steps
  1. Step 1: Look for a vertex of degree 1

    The Jetty has degree 1 — only the road from the Beach meets it.

Try a similar one

A fresh question of the same kind, checked as you answer, with hints and a full solution.

Method

  1. A vertex of degree 1 rules out a Hamiltonian cycle and must be an end of any Hamiltonian path.

  2. 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.

Save your progress with a free account