Skip to main content
🔗

Section 5.7 Hamiltonian Graphs

🔗
Recall that a graph that contains a trail that traverses all its edges is called an Eulerian graph.

🔗
Sometimes we would like a graph to have a cycle that passes through all of its vertices in some order, without repeating any vertex. These graphs are called Hamiltonian graphs.

🔗
Definition 5.7.1. Hamiltonian Cycle; Graph.

Let G=(V,E) be a simple graph. A Hamiltonian cycle on G is a cycle C that contains all the vertices of G.

A graph that contains a Hamiltonian cycle is called a Hamiltonian graph.

This graph from Example 5.4.13 is Hamiltonian, since it contains a Hamiltonian cycle \(s\)-\(p\)-\(t\)-\(q\)-\(u\)-\(r\)-\(s\text{.}\)

🔗
While it is very easy to determine whether a graph is Eulerian (just check that all its vertices have even degree!), it is generally very difficult to determine whether or not a graph is Hamiltonian.

Hamiltonian cycles are named after Irish mathematician Sir William Rowan Hamilton. In 1857 he invented what he called the icosian game, essentially a puzzle with the graph of a dodecahedron's vertices and edges, with the objective of finding a cycle through the graph that visits all vertices exactly once.

Can you find a Hamiltonian cycle in Hamilton's icosian game below?

🔗
Exploration 5.7.1. Knight's Tours.

Hamilton was not the first person to consider the problem of finding Hamiltonian cycles in a graph. This problem arose much earlier in a different context—that of finding a ‘knight's tour’ on a chessboard. That is, can a knight start at any square on a board, visit every square exactly once, and return to its starting position?

A knight on an otherwise empty eight-by-eight chessboard.
🔗
(b)

Explain how the knight's tour problem is equivalent to finding a Hamiltonian cycle on a graph (and explain how the graph is obtained).

🔗
(c)

Mentions of the knight's tour problem can be found as far back as the 9th century AD, in Sanskrit writings about poetics, and even before that for smaller grids. See [4] for a comprehensive timeline.

Try changing the size of the chessboard in this link to something smaller. Are there configurations that don't allow knight's tours?

🔗
In order to prove a graph is not Hamiltonian, one has to argue that it does not contain a Hamiltonian cycle as a subgraph (or, to assume that it does, and show it leads to a contradiction).

Consider the following graph:

If \(G\) had a Hamiltonian cycle \(C\text{,}\) it must contain both edges \((6,3)\) and \((6,5)\text{,}\) since these are the only two edges passing through 6. Similarly, \(C\) must contain both \((1,5)\) and \((1,2)\text{,}\) and \((2,1)\) and \((2,3)\text{,}\) and \((4,5)\) and \((4,3)\) (there are no other options for choosing two edges incident to vertices 1, 2, and 4).

This is already a contradiction, since we have argued that \(C\) must contain seven edges, while a Hamiltonian cycle in \(G\) will have only 6 edges. Hence \(G\) is not Hamiltonian.

🔗
The Traveling Salesman Problem generalizes the problem of finding a Hamiltonian cycle in a graph—when numbers called costs are assigned to the edges of a graph, one can also ask the question:

Find a Hamiltonian cycle of least cost on the graph G.

🔗
We also call these numbers distances or weights, and we want to minimize total distance or total weight of the Hamiltonian cycle.

In the following graph (numbers on edges are weights), find two different Hamiltonian cycles and compute their total costs. Can you find the least cost Hamiltonian cycle on this graph?

Explain how the problem in Checkpoint 5.1.4 relates to the Traveling Salesman Problem.

🔗
We end this section with a sufficient condition for a graph to be Hamiltonian, due to Dirac. Before working through the proof, attempt the checkpoints that follow first.

Let \(G = (V,E)\) be a graph on \(n = |V| \geq 3\) vertices, such that \(\min_v \deg(v) \geq n/2\text{.}\) Then \(G\) must be connected (by Exercise 5.8.27).

Let \(P = x_1x_2\cdots x_k\) be a longest path in \(G\) (note it has \(k-1\) edges).

Then all vertices of \(G\) that are adjacent to \(x_1\) must already be on \(P\text{,}\) otherwise, \(P\) can be extended to a longer path. Similarly, all vertices adjacent to \(x_k\) must already be on \(P\text{.}\) Because the minimum vertex degree is \(n/2\text{,}\) this means:

  • The vertex \(x_1\) is adjacent to \(n/2\) of the vertices \(\{x_2,x_3,\ldots,x_k\}\text{;}\)
  • and the vertex \(x_k\) is adjacent to \(n/2\) of the vertices \(\{x_1,x_2,\ldots,x_{k-1}\}\text{.}\)

Since \(k \leq n\text{,}\) there must be some pair of vertices \(x_{i+1}\) and \(x_i\) such that \((x_1,x_{i+1}) \in E\) and \((x_i,x_k) \in E\text{.}\) This is because there are \(n/2\) neighbours of \(x_1\) in the set \(\{x_2,\ldots,x_k\}\text{,}\) and hence only \(k - 1 - n/2\) of the set \(\{x_1,\ldots,x_{k-1}\}\) do not precede some neighbour of \(x_1\text{.}\)

Since \(k \leq n\text{,}\) then \(k - 1 - n/2 \leq n/2-1\text{,}\) which implies \(x_k\) must have a neighbour \(x_i\) that immediately precedes a neighbour of \(x_{1}\text{.}\)

We claim that the cycle

\begin{equation*} C = x_1x_{i+1}x_{i+2} \cdots x_kx_ix_{i-1}\cdots x_2x_1 \end{equation*}

contains all vertices of \(G\text{,}\) and is therefore a Hamiltonian cycle on \(G\text{.}\)

If not, since \(G\) is connected, there must be some vertex \(x_j\) on this cycle that is adjacent to some vertex \(y\) not on \(C\text{.}\) But now we can construct a path starting at \(y\text{,}\) moving to \(x_j\text{,}\) then following the cycle \(C\) for \(k-1\) more edges, creating a new path with \(k\) edges. This contradicts the fact that \(x_1x_2\cdots x_k\) was the longest path on \(G\text{.}\)

Hence \(C\) must be a Hamiltonian cycle on \(G\text{,}\) and \(G\) is Hamiltonian.

Verify that the following graph satisfies the conditions of Theorem 5.7.7, then find a Hamiltonian cycle on the graph.

Theorem 5.7.7 is a sufficient condition for a graph to be Hamiltonian, but it is not necesssary. Can you find an example of a Hamiltonian graph \(G\) that does not satisfy the conditions of the theorem?