Hamiltonian Graph — Definition, Formula & Examples

A Hamiltonian graph is a graph that contains a Hamiltonian cycle — a closed path that visits every vertex exactly once before returning to the starting vertex.

A graph $G = (V, E)$ is Hamiltonian if there exists a cycle $C$ in $G$ that includes every vertex $v \in V$ exactly once. Equivalently, $G$ contains a spanning cycle. A graph that contains a Hamiltonian path (visiting every vertex exactly once) but no Hamiltonian cycle is called traceable but not Hamiltonian.

How It Works

To determine whether a graph is Hamiltonian, you look for a cycle that passes through every vertex exactly once. There is no efficient general algorithm for this — the problem is NP-complete. However, 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. Ore's theorem generalizes this: if for every pair of non-adjacent vertices

u

and

v

\deg(u) + \deg(v) \geq n

, then the graph is Hamiltonian. These are sufficient but not necessary conditions, so a graph can be Hamiltonian without satisfying either theorem.

Worked Example

Problem: Determine whether the complete graph

K_5

(5 vertices, every pair connected) is Hamiltonian.

Check vertex degrees: In

K_5

, every vertex has degree 4. Since

n = 5

, we check Dirac's condition: each degree must be at least

\frac{n}{2}

\deg(v) = 4 \geq \frac{5}{2} = 2.5

Apply Dirac's theorem: The condition is satisfied for all vertices, so Dirac's theorem guarantees a Hamiltonian cycle exists.

Exhibit a Hamiltonian cycle: Label the vertices

1, 2, 3, 4, 5

. One Hamiltonian cycle is the sequence below, which visits every vertex exactly once and returns to the start.

1 \to 2 \to 3 \to 4 \to 5 \to 1

Answer:

K_5

is Hamiltonian. One Hamiltonian cycle is

1 \to 2 \to 3 \to 4 \to 5 \to 1

Why It Matters

The Hamiltonian cycle problem is the foundation of the famous Traveling Salesman Problem, which seeks the shortest Hamiltonian cycle in a weighted graph. It appears in logistics, circuit design, and genome sequencing. Understanding Hamiltonicity is essential in any discrete mathematics or algorithms course.

Common Mistakes

Mistake: Confusing Hamiltonian with Eulerian. Students often mix up visiting every vertex once (Hamiltonian) with traversing every edge once (Eulerian).

Correction: A Hamiltonian cycle covers all vertices; an Eulerian circuit covers all edges. A graph can be one, both, or neither.