Hamiltonian Cycle Backtracking

A Bit of History

Hamiltonian Cycle, Hamiltonian Path, and TSP

For a simple undirected graph, a Hamiltonian cycle has at least three vertices. The repeated start vertex is normally shown only to make closure explicit: $[0,1,2,3,0]$ represents three distinct visited vertices plus the return edge.

Choose, Explore, Undo

1. Break rotational symmetry. Fix vertex 0 as the start; any Hamiltonian cycle can be rotated to begin there.
2. Choose. From the current endpoint, append one adjacent unvisited vertex and mark it used.
3. Explore. Recurse. If all vertices are present, accept only when the endpoint connects to the start.
4. Undo. If the branch fails, remove the last vertex, clear its visited flag, and try the next candidate.
5. Stop or exhaust. Return the first cycle found, or report failure after every candidate prefix has been ruled out.

Visual Path Walkthrough

Both panels use the same six-vertex graph: a hexagon plus chords $0$–$2$ and $2$–$4$. Choosing neighbor 1 leads directly around the outer cycle. Choosing chord $0$–$2$, then $2$–$4$, then $4$–$3$ traps the endpoint because both neighbors of 3 are already used.

The Search Tree, Not Just the Graph

The algorithm explores a second structure: a tree whose nodes are partial paths. A graph vertex may appear in many search-tree nodes because it can be reached under different visited sets. Backtracking is depth-first traversal of this implicit tree.

Safe Pruning Rules

Necessary Conditions vs. Sufficient Theorems

Necessary checks can quickly prove no: connectivity, minimum degree at least two, absence of bridges and articulation points, and—in a bipartite graph—equal partition sizes. None of these alone proves a cycle exists.

Sufficient theorems can quickly prove yes. For a simple graph with $n\ge3$, Dirac’s condition $deg(v)\ge n/2$ for every vertex guarantees Hamiltonicity. Ore’s condition $deg(u)+\deg(v)\ge n$ for every nonadjacent pair also guarantees it. Graphs can be Hamiltonian without satisfying either condition, so failure of the theorem’s premise means “unknown,” not “no.”

Implementation

The following versions target simple undirected graphs represented by an adjacency matrix. They fix start vertex 0, restore state on every failed branch, reject graphs with fewer than three vertices, and return the repeated start vertex so the closing edge is visible.

def hamiltonian_cycle(n, adj_matrix):
    """
    n: number of vertices
    adj_matrix: n x n boolean adjacency matrix
    Returns a Hamiltonian cycle as a list of vertices, or None if none exists.
    """
    if n < 3:
        return None  # simple undirected cycles need at least 3 vertices

    path = [0]  # fix the starting vertex (WLOG)
    visited = [False] * n
    visited[0] = True

    def backtrack():
        if len(path) == n:
            # All vertices placed; check the closing edge back to start
            return adj_matrix[path[-1]][path[0]]

        last = path[-1]
        for candidate in range(n):
            if not visited[candidate] and adj_matrix[last][candidate]:
                path.append(candidate)
                visited[candidate] = True

                if backtrack():
                    return True

                # Backtrack: undo this choice
                path.pop()
                visited[candidate] = False

        return False

    if backtrack():
        return path + [path[0]]  # show the closing edge explicitly
    return None

# Example: pentagon (0-1-2-3-4-0) plus diagonal 0-2
n = 5
adj = [[False] * n for _ in range(n)]
edges = [(0,1), (1,2), (2,3), (3,4), (4,0), (0,2)]
for u, v in edges:
    adj[u][v] = adj[v][u] = True

result = hamiltonian_cycle(n, adj)
print("Hamiltonian cycle:", result)

#include <iostream>
#include <vector>

using namespace std;

bool backtrack(int n, vector<vector<bool>>& adj, vector<int>& path, vector<bool>& visited) {
    if ((int)path.size() == n) {
        return adj[path.back()][path[0]];
    }

    int last = path.back();
    for (int candidate = 0; candidate < n; candidate++) {
        if (!visited[candidate] && adj[last][candidate]) {
            path.push_back(candidate);
            visited[candidate] = true;

            if (backtrack(n, adj, path, visited)) return true;

            path.pop_back();
            visited[candidate] = false;
        }
    }
    return false;
}

vector<int> hamiltonianCycle(int n, vector<vector<bool>>& adj) {
    if (n < 3) return {};
    vector<int> path = {0};
    vector<bool> visited(n, false);
    visited[0] = true;

    if (backtrack(n, adj, path, visited)) {
        path.push_back(path[0]);
        return path;
    }
    return {};
}

int main() {
    int n = 5;
    vector<vector<bool>> adj(n, vector<bool>(n, false));
    vector<pair<int,int>> edges = {{0,1},{1,2},{2,3},{3,4},{4,0},{0,2}};
    for (auto& e : edges) {
        adj[e.first][e.second] = adj[e.second][e.first] = true;
    }

    vector<int> result = hamiltonianCycle(n, adj);
    cout << "Hamiltonian cycle: ";
    for (int v : result) cout << v << " ";
    cout << endl;
    return 0;
}

import java.util.*;

public class HamiltonianCycle {
    static boolean backtrack(int n, boolean[][] adj, List<Integer> path, boolean[] visited) {
        if (path.size() == n) {
            return adj[path.get(path.size() - 1)][path.get(0)];
        }

        int last = path.get(path.size() - 1);
        for (int candidate = 0; candidate < n; candidate++) {
            if (!visited[candidate] && adj[last][candidate]) {
                path.add(candidate);
                visited[candidate] = true;

                if (backtrack(n, adj, path, visited)) return true;

                path.remove(path.size() - 1);
                visited[candidate] = false;
            }
        }
        return false;
    }

    public static List<Integer> solve(int n, boolean[][] adj) {
        if (n < 3) return null;
        List<Integer> path = new ArrayList<>();
        path.add(0);
        boolean[] visited = new boolean[n];
        visited[0] = true;

        if (backtrack(n, adj, path, visited)) {
            path.add(path.get(0));
            return path;
        }
        return null;
    }

    public static void main(String[] args) {
        int n = 5;
        boolean[][] adj = new boolean[n][n];
        int[][] edges = {{0,1},{1,2},{2,3},{3,4},{4,0},{0,2}};
        for (int[] e : edges) {
            adj[e[0]][e[1]] = true;
            adj[e[1]][e[0]] = true;
        }

        List<Integer> result = solve(n, adj);
        System.out.println("Hamiltonian cycle: " + result);
    }
}

Complexity and Exact Alternatives

Fixing the start removes rotational duplicates, leaving at most $(V-1)!$ vertex orders. Backtracking can still explore a factorial number of prefixes in adversarial graphs:

The auxiliary space covers the path, visited set, and recursion stack. The shown adjacency matrix itself occupies $O(V^2)$. A memoized subset dynamic program—often associated with Held–Karp—trades memory for a better exact bound of roughly $O(V^2 2^V)$ time and $O(V2^V)$ space.

Hamiltonian vs. Eulerian: Do Not Mix Them Up

Real-World Applications

Real routing and drilling systems usually optimize distance on a weighted graph, making them TSP variants rather than plain Hamiltonian-cycle decision problems. Genome assembly also largely moved from fragment-overlap Hamiltonian formulations toward Eulerian walks in de Bruijn graphs. These connections are best understood as modeling history and shared structure, not identical problems.

Exercises

Limitations

Use backtracking when graphs are small, structured, or aggressively constrained. For larger exact instances, compare subset DP and modern SAT/ILP/constraint-programming solvers before committing to a hand-built search.