9.19 Hamiltonian Paths

You need to visit every vertex exactly once.

algorithmsgraphsgraph-theory

9.19 Hamiltonian Paths

Problem

You need to visit every vertex exactly once.

Many graph problems focus on covering all vertices rather than all edges.

Examples include:

  • Visiting every city in a tour
  • Scheduling visits to every location
  • Traversing every checkpoint
  • Planning routes through attractions
  • Sequencing tasks with transition constraints

Unlike Euler paths, which use every edge exactly once, these problems care about vertices.

You need to determine whether a traversal exists that visits every vertex exactly once.

Solution

Use a Hamiltonian path.

A Hamiltonian path is a path that visits every vertex exactly once.

A Hamiltonian cycle is a Hamiltonian path that returns to its starting vertex.

Example:

A -- B -- C -- D

Hamiltonian path:

A → B → C → D

Every vertex appears exactly once.

Now consider:

A -- B
|    |
D -- C

Hamiltonian cycle:

A → B → C → D → A

Every vertex appears once, and the path returns to the start.

Discussion

Hamiltonian paths and Euler paths are frequently confused.

The distinction is fundamental.

Problem Requirement
Euler path Visit every edge exactly once
Hamiltonian path Visit every vertex exactly once

Consider:

A -- B -- C

The traversal:

A → B → C

is both Eulerian and Hamiltonian.

However, the two concepts quickly diverge.

Example:

    A
   /|\\n  B C D

A Hamiltonian path exists:

B → A → C

but it cannot visit every edge.

Conversely, many Eulerian graphs contain no Hamiltonian cycle.

The problems are fundamentally different.

Why Hamiltonian Problems Are Difficult

Euler path existence can be checked using degree conditions.

Hamiltonian paths have no comparable simple characterization.

For example:

A -- B -- C -- D

has a Hamiltonian path.

Now add one edge:

A -- B -- C
|         |
+---------+

A Hamiltonian cycle exists.

The addition of a single edge changes the problem dramatically.

Unlike Euler paths, local information such as vertex degree is often insufficient.

The difficulty of Hamiltonian problems is one reason they play a central role in complexity theory.

Brute Force Approach

The simplest strategy tries every possible ordering.

Suppose:

n vertices

exist.

There are:

n!

possible vertex permutations.

For each permutation:

  1. Check whether consecutive vertices are connected.
  2. Verify that every vertex appears exactly once.

Example:

from itertools import permutations

def hamiltonian_path(graph):
    vertices = list(graph)

    for path in permutations(vertices):
        valid = True

        for i in range(len(path) - 1):
            if path[i + 1] not in graph[path[i]]:
                valid = False
                break

        if valid:
            return list(path)

    return None

This works for very small graphs.

It becomes impractical quickly.

A more efficient approach builds the path incrementally.

Instead of generating all permutations, extend only valid partial paths.

def hamiltonian_path(graph):
    n = len(graph)

    def search(path, visited):
        if len(path) == n:
            return path

        current = path[-1]

        for neighbor in graph[current]:
            if neighbor not in visited:
                result = search(
                    path + [neighbor],
                    visited | {neighbor}
                )

                if result:
                    return result

        return None

    for start in graph:
        result = search(
            [start],
            {start}
        )

        if result:
            return result

    return None

This approach avoids exploring impossible branches.

For many practical instances, it performs much better than brute force.

Example

Consider:

graph = {
    "A": ["B", "D"],
    "B": ["A", "C"],
    "C": ["B", "D"],
    "D": ["A", "C"],
}

Result:

[
    "A",
    "B",
    "C",
    "D"
]

Every vertex appears exactly once.

The path is Hamiltonian.

Hamiltonian Cycles

A Hamiltonian cycle returns to the starting vertex.

After constructing a Hamiltonian path:

A → B → C → D

verify:

D → A

exists.

If so:

A → B → C → D → A

is a Hamiltonian cycle.

The verification is simple.

def is_hamiltonian_cycle(graph, path):
    if len(path) != len(graph):
        return False

    return path[0] in graph[path[-1]]

Complete Graphs

A complete graph contains every possible edge.

Example:

A -- B
|\  /|
| \/ |
| /\ |
|/  \|
C -- D

Every pair of vertices is connected.

Every complete graph with at least three vertices contains a Hamiltonian cycle.

Example:

A → B → C → D → A

Many such cycles exist.

Complete graphs are therefore the easiest Hamiltonian graphs.

Trees

Trees provide an interesting contrast.

Consider:

    A
   / \\n  B   C

A Hamiltonian path exists:

B → A → C

Now consider:

      A
    / | \\n   B  C  D

No Hamiltonian path exists.

Once you leave:

B

you cannot return.

The branching structure prevents visiting every leaf exactly once.

Trees rarely contain Hamiltonian cycles.

In fact:

No tree with more than two vertices contains a Hamiltonian cycle.

The cycle would require an extra edge.

Degree Observations

Degree alone cannot determine Hamiltonicity.

However, some useful observations exist.

If a graph contains:

More than two vertices of degree one

then a Hamiltonian path is impossible.

Why?

Every degree-one vertex must appear at an endpoint of the path.

A path has only two endpoints.

Therefore:

Degree-one vertices > 2

immediately rules out a Hamiltonian path.

This is a useful pruning rule.

Directed Hamiltonian Paths

The concept extends naturally to directed graphs.

Example:

A → B → C → D

Hamiltonian path:

A → B → C → D

The direction must be respected.

The backtracking algorithm changes only slightly.

Neighbor expansion follows outgoing edges.

Everything else remains the same.

Traveling Salesman Connection

Hamiltonian cycles form the basis of the Traveling Salesman Problem (TSP).

Suppose:

Cities = vertices
Roads = edges

A Hamiltonian cycle visits every city exactly once.

TSP adds weights:

Distance
Cost
Time

and asks:

Which Hamiltonian cycle has minimum total cost?

This transforms a feasibility problem into an optimization problem.

Many route-planning systems build upon this idea.

def hamiltonian_cycle(graph):
    n = len(graph)

    def search(path, visited):
        if len(path) == n:
            if path[0] in graph[path[-1]]:
                return path + [path[0]]
            return None

        current = path[-1]

        for neighbor in graph[current]:
            if neighbor not in visited:
                result = search(
                    path + [neighbor],
                    visited | {neighbor}
                )

                if result:
                    return result

        return None

    for start in graph:
        result = search(
            [start],
            {start}
        )

        if result:
            return result

    return None

Example:

[
    "A",
    "B",
    "C",
    "D",
    "A"
]

This is a Hamiltonian cycle.

Complexity Analysis

Unlike BFS, DFS, or shortest-path algorithms, Hamiltonian path search is generally exponential.

For a graph with:

n vertices

the search space may approach:

O(n!)

or:

O(2ⁿ · n)

depending on implementation.

Method Complexity
Brute force permutations O(n!)
Backtracking Exponential worst case
Dynamic programming (Held-Karp) O(2ⁿ · n²)
BFS O(V + E)
DFS O(V + E)

This dramatic difference is why Hamiltonian problems are considered computationally difficult.

Common Pitfalls

Do not confuse Hamiltonian paths with Euler paths.

Do not assume high connectivity guarantees a Hamiltonian cycle.

Do not use degree parity rules from Euler graphs.

Those rules do not apply.

Do not forget to verify the closing edge when searching for a Hamiltonian cycle.

Do not expect polynomial-time algorithms for arbitrary graphs.

Do not revisit vertices during the search.

The entire definition depends on visiting each vertex exactly once.

Recipe: Validate a Hamiltonian Path

Given a candidate path:

def validate_hamiltonian_path(
    graph,
    path
):
    if len(path) != len(graph):
        return False

    if len(set(path)) != len(graph):
        return False

    for i in range(len(path) - 1):
        if path[i + 1] not in graph[path[i]]:
            return False

    return True

This is useful for testing generated solutions.

Takeaway

Hamiltonian paths visit every vertex exactly once, while Hamiltonian cycles additionally return to the starting vertex. Unlike Euler problems, which have elegant degree-based characterizations, Hamiltonian problems are significantly more difficult and often require exponential-time search. Despite their computational complexity, they appear naturally in routing, scheduling, logistics, circuit design, and optimization problems such as the Traveling Salesman Problem. Understanding Hamiltonian paths provides an important introduction to graph-search problems where global structure matters more than local properties.