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 AA–BB–CC–DD–EE–FF–AA 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?

Choose one answer
Interactive

Find a round trip

Start at TT, visit every other vertex exactly once and return to TT. 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 nn vertices uses exactly nn edges.

Finding the shortest Hamiltonian cycle

  1. Fix the starting vertex

    Every cycle passes through the base, so start every trial there.

  2. List the cycles systematically

    Group them by the pair of edges they use at the starting vertex.

  3. Prune

    Skip orders that need an edge the graph does not have, and use any edges forced by vertices of degree 2.

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

  • Complex familiar

A mobile vet based in town TT must visit four farms, PP, QQ, RR and SS, once each and then return to TT. Travel times, in minutes, are shown. Find the quickest round trip and its total time.

6 steps

Try it yourself first, then check the working one step at a time.

Method

  1. List the Hamiltonian cycles systematically, grouped by the pair of edges used at the starting vertex.

  2. Count a cycle and its reverse once.

  3. Total each cycle and choose the least.

Watch out for

  • Forgetting the return leg. The path TT–PP–QQ–RR–SS takes 36 minutes, but the trip is not over until the vet is back at TT.

Four towns WW, XX, YY and ZZ are each joined directly to the other three. The distances are WX=10WX = 10, WY=15WY = 15, WZ=20WZ = 20, XY=35XY = 35, XZ=25XZ = 25 and YZ=30YZ = 30 km. Find the length of the shortest Hamiltonian cycle.

in km

Worked example

A dead-end road makes a graph semi-Hamiltonian

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

4 steps

Try it yourself first, then check the working one step at a time.

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.

Which statement is true for this network of walking tracks?

Choose one answer

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.

Lesson 8 of 80% read

Save your progress with a free account