Graph theory · Definition

Hamiltonian cycle

discrete mathematicsgraphs

Before you start you need to know

It is the problem of visiting every place in a network exactly once and returning; it lies behind the traveling salesman problem.

Definition

A Hamiltonian cycle of a graph \(G\) with \(n\ge 3\) vertices is a cycle that visits every vertex of \(G\) exactly once.

\[\deg(v)\ge \tfrac n2\ \forall v\ \Longrightarrow\ \text{Hamiltonian cycle exists}\]

Unlike the Eulerian case, no simple characterization is known: deciding whether a graph is Hamiltonian is NP-complete. There are sufficient conditions, though. Dirac's theorem guarantees the cycle if every vertex has degree at least \(n/2\), and Ore's does so if \(\deg(u)+\deg(v)\ge n\) for every pair of non-adjacent vertices.

There are also easy obstructions. A vertex of degree 1 prevents it, since a cycle needs two edges at each vertex. A cut vertex prevents it too, as in the bowtie. And in a bipartite graph the two parts must have equal size, since the cycle alternates between them; hence \(K_{2,3}\) is not Hamiltonian while \(K_{3,3}\) is.

Guiding example: \(K_n\) with \(n\ge 3\) is Hamiltonian and has \((n-1)!/2\) distinct cycles; the cube \(Q_3\) is, via the Gray code \(000,001,011,010,110,111,101,100\). A typical mistake is to believe Eulerian and Hamiltonian cycles imply each other: they concern edges and vertices respectively, and neither implies the other.

Think about it

Why does \(K_{2,3}\) have no Hamiltonian cycle?

Because a cycle in a bipartite graph alternates between the parts, and parts of sizes 2 and 3 cannot alternate to cover all 5 vertices.

Exercises 10

  1. How many distinct Hamiltonian cycles does \(K_5\) have, not counting the starting vertex or direction?
  2. Which of these graphs has a Hamiltonian cycle?
  3. Which of these complete bipartite graphs has a Hamiltonian cycle?
  4. A simple graph has 8 vertices and each has degree at least 4. What can be guaranteed?
  5. A Hamiltonian cycle of a graph with 9 vertices uses how many edges?
  6. The bowtie is two triangles sharing one vertex (5 vertices). Which is true?
  7. Which condition prevents a graph from having a Hamiltonian cycle?
  8. In the cube \(Q_3\) (vertices: 3-bit strings; edges: strings differing in one bit), which list is a Hamiltonian cycle?
  9. A bipartite graph has parts of 4 and 5 vertices. Can it have a Hamiltonian cycle?
  10. What is the relation between having an Eulerian cycle and having a Hamiltonian cycle?

References

  • Kenneth H. Rosen, Discrete Mathematics and Its Applications, 8th edition, McGraw-Hill, 2019. §10.5
  • Susanna S. Epp, Discrete Mathematics with Applications, 5th edition, Cengage, 2019. §10.2
  • Ralph P. Grimaldi, Discrete and Combinatorial Mathematics: An Applied Introduction, 5th edition, Pearson, 2003. §11.6