Hamiltonian Path — Definition, Formula & Examples

A Hamiltonian path is a path in a graph that visits every vertex exactly once. If such a path exists that starts and ends at the same vertex, it is called a Hamiltonian cycle.

Given a graph $G = (V, E)$ with $n$ vertices, a Hamiltonian path is a sequence of $n$ distinct vertices $v_1, v_2, \dots, v_n$ such that $(v_i, v_{i+1}) \in E$ for all $1 \leq i \leq n-1$ . A Hamiltonian cycle additionally requires $(v_n, v_1) \in E$ .

How It Works

To determine whether a graph has a Hamiltonian path, you try to find an ordering of all vertices so that each consecutive pair is connected by an edge. Unlike Eulerian paths (which traverse every edge), Hamiltonian paths must hit every vertex. There is no efficient general algorithm known for finding Hamiltonian paths; the problem is NP-complete. For small graphs, you can check by systematic trial or backtracking. Sufficient conditions exist — for example, Dirac's theorem guarantees a Hamiltonian cycle in a simple graph on

n \geq 3

vertices if every vertex has degree at least

\frac{n}{2}

Worked Example

Problem: Determine whether the graph with vertices {A, B, C, D} and edges {AB, AC, BC, BD, CD} has a Hamiltonian path.

Step 1: List the adjacencies. A connects to B, C. B connects to A, C, D. C connects to A, B, D. D connects to B, C.

Step 2: Try a path starting at A. Go A → B (edge AB exists), then B → D (edge BD exists), then D → C (edge CD exists). This visits all four vertices exactly once.

A \to B \to D \to C

Step 3: Verify: the path uses three edges and passes through all four vertices without repetition.

Answer: Yes. A → B → D → C is a Hamiltonian path.

Why It Matters

Hamiltonian path problems model real-world routing tasks such as the Traveling Salesman Problem, where a salesperson must visit every city exactly once at minimum cost. Understanding Hamiltonian paths is also central to computational complexity theory, since deciding their existence is one of the classic NP-complete problems.

Common Mistakes

Mistake: Confusing a Hamiltonian path (visits every vertex once) with an Eulerian path (traverses every edge once).

Correction: Remember: Hamiltonian concerns vertices, Eulerian concerns edges. A graph can have one without the other.