Hamiltonian Cycle — Definition, Formula & Examples

A Hamiltonian cycle is a path through a graph that starts at one vertex, visits every other vertex exactly once, and returns to the starting vertex. A graph that contains such a cycle is called Hamiltonian.

Given a graph $G = (V, E)$ with $|V| = n$ , a Hamiltonian cycle is a cycle $v_1, v_2, \ldots, v_n, v_1$ such that every vertex in $V$ appears exactly once in the sequence $v_1, v_2, \ldots, v_n$ and each consecutive pair $(v_i, v_{i+1})$ as well as $(v_n, v_1)$ is an edge in $E$ .

How It Works

To check whether a graph has a Hamiltonian cycle, you look for a way to traverse all vertices exactly once and return to your starting point using only existing edges. There is no known efficient (polynomial-time) algorithm for this in general — determining whether a Hamiltonian cycle exists is a classic NP-complete problem. For small graphs, you can attempt a systematic search or backtracking. Sufficient conditions exist: Dirac's theorem states that if every vertex in a simple graph on

n \geq 3

vertices has degree at least

\frac{n}{2}

, then the graph is Hamiltonian.

Worked Example

Problem: Determine whether the complete graph

K_4

(four vertices, each connected to every other) has a Hamiltonian cycle.

Label the vertices: Call the four vertices

A

B

C

, and

D

. Every pair of distinct vertices shares an edge.

Construct a cycle visiting each vertex once: Start at

A

, go to

B

, then

C

, then

D

, and return to

A

. The path is

A \to B \to C \to D \to A

Verify: Each vertex appears exactly once before returning to

A

, and every consecutive pair is an edge in

K_4

. This is a valid Hamiltonian cycle.

Answer: Yes,

K_4

has a Hamiltonian cycle, for example

A \to B \to C \to D \to A

Why It Matters

The Hamiltonian cycle problem is a foundational example in computational complexity, used to prove NP-completeness of other problems. It also underpins the Traveling Salesman Problem, which has direct applications in logistics, circuit board drilling, and DNA sequencing.

Common Mistakes

Mistake: Confusing a Hamiltonian cycle with an Eulerian circuit.

Correction: A Hamiltonian cycle visits every vertex exactly once; an Eulerian circuit traverses every edge exactly once. They impose fundamentally different requirements on the graph.