Hamiltonian Walk — Definition, Formula & Examples

A Hamiltonian walk is a closed walk in a graph that visits every vertex at least once, though it may repeat vertices and edges. Unlike a Hamiltonian cycle, it does not require that each vertex be visited exactly once.

Given a graph $G = (V, E)$ , a Hamiltonian walk is a closed walk $v_0, e_1, v_1, e_2, \ldots, e_k, v_k$ where $v_0 = v_k$ and every vertex $v \in V$ appears as some $v_i$ for at least one index $i$ . Edges and vertices may be repeated.

How It Works

To find a Hamiltonian walk, you start at any vertex and traverse edges, visiting every vertex in the graph at least once, then return to your starting vertex. You are allowed to revisit vertices and reuse edges. This makes Hamiltonian walks easier to find than Hamiltonian cycles, since the exactness constraint is relaxed. Every graph that has a Hamiltonian cycle automatically has a Hamiltonian walk, but the converse is not true. The length of an optimal (shortest) Hamiltonian walk in a weighted graph is closely related to the Travelling Salesman Problem.

Worked Example

Problem: Consider the graph with vertices

\{A, B, C, D\}

and edges

\{AB, BC, CD, AD, AC\}

. The edge

BD

does not exist. Find a Hamiltonian walk starting and ending at

A

Step 1: Start at

A

. Traverse to

B

via edge

AB

, then to

C

via edge

BC

, then to

D

via edge

CD

. All vertices have now been visited.

A \to B \to C \to D

Step 2: Return to

A

via edge

AD

to close the walk.

D \to A

Step 3: Check: every vertex (

A, B, C, D

) appears at least once, and the walk is closed since it starts and ends at

A

. This walk happens to also be a Hamiltonian cycle since no vertex is repeated (other than the start/end). In a graph without edge

AD

, you would need to repeat a vertex, producing a Hamiltonian walk that is not a Hamiltonian cycle.

Answer: A Hamiltonian walk is

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

, with total length 4 edges.

Why It Matters

Hamiltonian walks arise naturally when modeling routing problems where you must visit every location but can afford to retrace steps. Optimizing the length of a Hamiltonian walk in weighted graphs is a variant of the Travelling Salesman Problem studied in combinatorial optimization and operations research.

Common Mistakes

Mistake: Confusing a Hamiltonian walk with a Hamiltonian cycle by assuming every vertex must be visited exactly once.

Correction: A Hamiltonian walk allows repeated vertices and edges. A Hamiltonian cycle requires each vertex to appear exactly once (except the start/end vertex). Every Hamiltonian cycle is a Hamiltonian walk, but not vice versa.