Lesson 8 of 8 · 17 min
Hamiltonian paths and cycles
Find routes that visit every vertex exactly once, decide whether a graph is Hamiltonian or semi-Hamiltonian, and find the shortest Hamiltonian cycle in a small network by trial and error.
What you will be able to do
- Define Hamiltonian path, Hamiltonian cycle, Hamiltonian graph and semi-Hamiltonian graph.
- Find Hamiltonian paths and cycles by systematic trial and error.
- Use vertices of degree 1 and 2 to rule out or force parts of a Hamiltonian cycle.
- Find the shortest Hamiltonian cycle in a small weighted graph.
A courier does not need to drive down every road. She needs to reach every customer once and get back to the depot.
Visiting every vertex exactly once is a different problem from covering every edge, and it has a different name: Hamiltonian, after the Irish mathematician William Rowan Hamilton.
Definition
Hamiltonian paths, cycles and graphs
- A Hamiltonian path is a path that visits every vertex of the graph exactly once.
- A Hamiltonian cycle is a cycle that visits every vertex exactly once and returns to its starting vertex.
- A graph with a Hamiltonian cycle is a Hamiltonian graph.
- A graph with a Hamiltonian path but no Hamiltonian cycle is a semi-Hamiltonian graph.
A Hamiltonian route does not have to use every edge.
Eulerian
- Every edge exactly once
- Vertices may be revisited
- Degrees decide: count the odd vertices
- A street sweeper's route
Hamiltonian
- Every vertex exactly once
- Edges may be left unused
- No simple test: trial and error
- A courier's delivery run
The hexagon –––––– is a Hamiltonian cycle, so this graph is Hamiltonian. The dashed edges are not needed. (The same graph is semi-Eulerian — the two ideas are independent.)
In the graph above (using all of its edges, dashed or not), which of these is a Hamiltonian path?
Start at , visit every other vertex exactly once and return to . How many different round trips can you find, and which has the least total weight?
Key idea
Shortcuts for the trial and error
- A vertex of degree 1 rules out a Hamiltonian cycle, and must be an end of any Hamiltonian path.
- A vertex of degree 2 forces both of its edges into any Hamiltonian cycle.
- A cycle and its reverse are the same cycle with the same total, so list each once.
- A Hamiltonian cycle through vertices uses exactly edges.
Finding the shortest Hamiltonian cycle
Fix the starting vertex
Every cycle passes through the base, so start every trial there.
List the cycles systematically
Group them by the pair of edges they use at the starting vertex.
Prune
Skip orders that need an edge the graph does not have, and use any edges forced by vertices of degree 2.
Total and compare
Add the weights around each cycle, including the edge back to the start. State the cycle with the least total and its units.
Worked example
A vet's round trip — the shortest Hamiltonian cycle
A mobile vet based in town must visit four farms, , , and , once each and then return to . Travel times, in minutes, are shown. Find the quickest round trip and its total time.
Step 1: Recognise the problem
Visiting every vertex once and returning to the start is a Hamiltonian cycle. You want the one with the least total time.
Step 2: Organise the trial and error
is joined to , and , so the trip leaves along one of these edges and returns along another. A cycle and its reverse take the same time, so list each cycle once.
Step 3: Cycles that use TP and TQ
Visit and in between: ––––– takes min. (–––… is impossible: there is no edge .)
Step 4: Cycles that use TP and TS
––––– takes min, and ––––– takes min.
Step 5: Cycles that use TQ and TS
––––– takes min. The other order, –––––, would need the edge , which does not exist.
Step 6: Choose the least total
The quickest round trip is –––––, or its reverse, taking 56 minutes.
Try it yourself first, then check the working one step at a time.
Answer
––––– (or the reverse), taking 56 minutes.
Method
List the Hamiltonian cycles systematically, grouped by the pair of edges used at the starting vertex.
Count a cycle and its reverse once.
Total each cycle and choose the least.
Watch out for
Forgetting the return leg. The path –––– takes 36 minutes, but the trip is not over until the vet is back at .
Four towns , , and are each joined directly to the other three. The distances are , , , , and km. Find the length of the shortest Hamiltonian cycle.
Worked example
A dead-end road makes a graph semi-Hamiltonian
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.
Try it yourself first, then check the working one step at a time.
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.
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.
Which statement is true for this network of walking tracks?
Common mistake
Four ways to go wrong
- Repeating a vertex — then the route is no longer a path or a cycle.
- Thinking every edge must be used. That is the Eulerian problem.
- Listing a cycle and its reverse as two different cycles.
- Forgetting the final edge back to the start when totalling a cycle.
Exam tip
Questions often ask for the Hamiltonian cycle with the least total weight, starting at a given vertex. Write the cycle as a vertex sequence, such as WGPKNW, show the sum of its weights, and give the total with units. Listing the alternatives you compared shows your trial and error.
Summary
A Hamiltonian path visits every vertex exactly once; a Hamiltonian cycle also returns to its start.
A graph with a Hamiltonian cycle is Hamiltonian; one with a Hamiltonian path but no Hamiltonian cycle is semi-Hamiltonian.
There is no degree test — use systematic trial and error.
A vertex of degree 1 rules out a Hamiltonian cycle; a vertex of degree 2 forces both its edges into one.
To find the shortest Hamiltonian cycle, list the cycles from the start once each, total them, and choose the least.
Finished the lesson?
Try the 3 quick checks above and the lesson completes itself, or mark it complete now.