What Is a Hamiltonian Cycle? Every Vertex Once, Then Back Home

You have a graph. You want to tour every city (vertex) exactly once and return to where you started. Simple premise. Turns out, no computer on Earth can do this efficiently for large inputs. And no algorithm is coming to save you.

A Hamiltonian cycle is one of those ideas that feels like it should be easy and then punches you in the face with NP-completeness. Here's what you actually need to know.

The Definition Is Simple. The Problem Isn't.

A Hamiltonian cycle is a closed walk through a graph that visits every vertex exactly once before returning to the starting vertex.

Start at vertex A. Walk through the graph. Hit every other vertex once. Come back to A. That's it. If you can do it, you've found a Hamiltonian cycle.

Concrete example. Five vertices, five edges:

Five-vertex graph with a Hamiltonian cycle highlighted

One Hamiltonian cycle: 1 → 2 → 3 → 4 → 5 → 1. Every vertex visited once, path closes. Done.

Now tweak one edge. Remove 4-5, add 2-5:

1 -- 2 -- 3
     |    |
     5    4

No Hamiltonian cycle exists. Vertex 4 connects only to 3. Vertex 5 connects only to 2. There is no closed tour that hits every vertex once. The existence of a Hamiltonian cycle depends entirely on graph structure, and small changes can flip the answer completely. Graphs look like you should be able to solve them by staring hard enough. You can't.

Hamiltonian Cycle vs Eulerian Circuit: The Interview Trap

These two concepts fool people constantly, because they sound almost identical.

An Eulerian circuit visits every edge exactly once and returns to start. Euler cared about edges. Hamilton cared about vertices. That one-word difference is an enormous computational gap. Euler: polynomial time. Hamilton: no known polynomial algorithm, probably never will be.

Finding an Eulerian circuit takes O(V+E) time via Hierholzer's algorithm. A simple check (all vertices have even degree) tells you whether one exists. Fast, clean, solvable.

Finding a Hamiltonian cycle is NP-complete. No polynomial-time algorithm is known. The best exact algorithm is still exponential.

	Hamiltonian Cycle	Eulerian Circuit
Visits	Every vertex once	Every edge once
Easy existence check	No (NP-complete)	Yes (degree conditions)
Best algorithm	O(n² × 2^n)	O(V+E)
Practical limit	~20 vertices	Millions of edges

When an interviewer describes a graph traversal problem and asks you to classify it, this is the table to have in your head. Vertices once, cycle closed: Hamiltonian, NP-complete. Edges once, cycle closed: Eulerian, polynomial.

The Hamiltonian path problem is the open-walk version: visit every vertex once but you don't need to return to start. It's also NP-complete. The cycle variant just adds the return edge requirement.

Why It's Hard: A Quick NP-Complete Primer

Richard Karp proved in 1972 that Hamiltonian cycle is NP-complete. It was one of his original 21 NP-complete problems, published in what became one of the most cited papers in computer science.

NP-complete means two things simultaneously. First, any proposed solution (a list of vertices in order) can be verified in O(n) time. Just check that each consecutive pair shares an edge and that you visited every vertex once. Easy. Second, finding a solution in the first place has no known polynomial-time algorithm. Checking the answer is trivial. Finding the answer is a different sport entirely.

If you found a polynomial-time algorithm for Hamiltonian cycle, you would prove P=NP and collect $1 million from the Clay Mathematics Institute. No pressure.

Brute force enumerates all permutations and checks each one. O(n!) time. For n=20 vertices, roughly 2.4 quintillion operations. That's not an algorithmic bottleneck. That's physics saying no.

The Algorithms You Actually Need

Backtracking is the practical approach for small graphs (up to roughly 15-20 vertices). Build the path vertex by vertex, and back up whenever you hit a dead end.

def has_hamiltonian_cycle(graph: list[list[int]]) -> bool:
    n = len(graph)
    path = [0]
    visited = {0}

    def backtrack() -> bool:
        if len(path) == n:
            return graph[path[-1]][path[0]] == 1

        current = path[-1]
        for neighbor in range(n):
            if neighbor not in visited and graph[current][neighbor] == 1:
                path.append(neighbor)
                visited.add(neighbor)
                if backtrack():
                    return True
                path.pop()
                visited.remove(neighbor)

        return False

    return backtrack()

Worst case is still O(n!), but backtracking prunes entire subtrees. On sparse graphs, it terminates far earlier than the theoretical bound.

Held-Karp dynamic programming is the best known exact algorithm at O(n² × 2^n) time and O(n × 2^n) space. It uses bitmask DP to track which vertices have been visited. For n=20: about 400 million operations instead of 2.4 quintillion. Still exponential, but the polite kind. The kind that fits in a few seconds for n=20 instead of the heat death of the universe.

def min_hamiltonian_cycle(dist: list[list[float]]) -> float:
    n = len(dist)
    INF = float('inf')
    dp = [[INF] * n for _ in range(1 << n)]
    dp[1][0] = 0  # start at vertex 0

    for mask in range(1 << n):
        for u in range(n):
            if dp[mask][u] == INF or not (mask >> u & 1):
                continue
            for v in range(n):
                if mask >> v & 1:
                    continue
                new_mask = mask | (1 << v)
                dp[new_mask][v] = min(dp[new_mask][v], dp[mask][u] + dist[u][v])

    full_mask = (1 << n) - 1
    return min(dp[full_mask][u] + dist[u][0] for u in range(n))

The bitmask encodes the visited set. mask >> v & 1 checks whether vertex v has been visited. At the end, you close the cycle by returning to vertex 0 and take the minimum over all possible last vertices.

This is the Traveling Salesman Problem (TSP) algorithm. TSP is exactly Hamiltonian cycle on a weighted graph, asking for the minimum-cost tour. If you can solve minimum-cost Hamiltonian cycle, you've solved TSP. They're the same problem with edge weights added.

When a Hamiltonian Cycle Is Guaranteed to Exist

Two classical theorems give sufficient conditions for existence. Neither is necessary. There is no clean necessary-and-sufficient characterization for Hamiltonian cycles, and that asymmetry is itself a reflection of NP-completeness.

Dirac's theorem (1952): If every vertex in a graph with n ≥ 3 vertices has degree at least n/2, the graph has a Hamiltonian cycle. High connectivity everywhere guarantees a tour exists.

Ore's theorem (1960): If for every pair of non-adjacent vertices u and v, deg(u) + deg(v) ≥ n, then the graph has a Hamiltonian cycle. A generalization of Dirac's that applies even when individual degrees are lower.

Both are sufficient conditions, not necessary ones. A graph can have a Hamiltonian cycle without satisfying either theorem.

The Petersen graph is the famous counterexample. Every vertex has degree 3, the graph looks well-connected, and no Hamiltonian cycle exists. It's hypohamiltonian: remove any single vertex and the remaining graph becomes Hamiltonian. The full graph is not. "Well-connected" does not imply Hamiltonian. Don't trust a graph just because it looks friendly.

How It Shows Up in Coding Interviews

You will not be asked to write an efficient Hamiltonian cycle algorithm for a large graph. That algorithm does not exist.

What you will be asked:

First, classification. "Is this problem solvable efficiently?" If the problem reduces to finding a tour through every vertex on a closed path, the answer is: NP-complete, no polynomial algorithm, and you should say that out loud. Recognizing this fast is a senior-level signal. Saying "I don't think this is efficiently solvable" earns more points than silently grinding toward an approach that doesn't exist.

Second, backtracking for small inputs. "Given this graph with 10 vertices, determine if a Hamiltonian cycle exists." The backtracking implementation above is the expected approach. Practice it until the template is automatic.

Third, TSP variants. "What's the minimum-cost route visiting every city?" This is Held-Karp. The bitmask DP template above handles it. The connection between Hamiltonian cycle and the Traveling Salesman Problem is something interviewers at senior levels expect you to see immediately.

Fourth, the Euler/Hamilton contrast. "I have this traversal problem. What algorithm applies?" Knowing which word in the problem statement (edges vs vertices, open vs closed) determines whether you're in O(V+E) or NP-complete territory is a fundamental graph theory check.

NP-completeness and backtracking are two areas worth understanding deeply before your interviews, not just for Hamiltonian cycle but for the whole class of problems built on the same structure.

Practicing these classifications under pressure, while speaking out loud, is harder than it looks at a desk. SpaceComplexity runs voice-based mock interviews where you have to reason through graph problems in real time, not just code them in silence.

A £25 Puzzle, an NP-Complete Proof, 115 Years Apart

William Rowan Hamilton invented the Icosian Game in 1857. The game was a dodecahedron (a 20-sided solid) with each vertex labeled with a major world city: London, Paris, Dublin, and so on. The puzzle: start at one city and find a route visiting every other city exactly once before returning home.

Hamilton presented it at a British Association meeting in Dublin in August 1857 and later sold it to a game manufacturer, John Jaques and Son, for £25. He was one of the greatest mathematicians of the 19th century. He sold a toy for £25. He had absolutely no idea he'd just attached his name to one of the defining hard problems in computational complexity, and that computer scientists 115 years later would still be unable to efficiently solve the general version.

115 years later, Karp proved the problem Hamilton invented was NP-complete. The Icosian Game is still solvable by hand. The general problem remains unsolved. The puzzle Hamilton sold for the price of a decent coat is now immortalized in complexity theory.

Key Takeaways

A Hamiltonian cycle visits every vertex exactly once and returns to the start.
Eulerian circuits visit every edge once: polynomial. Hamiltonian cycles visit every vertex once: NP-complete. That's the core contrast.
Brute force is O(n!). Held-Karp DP is O(n² × 2^n). Backtracking sits between them in practice.
TSP is Hamiltonian cycle on a weighted graph. The same Held-Karp algorithm solves both.
In interviews: recognize NP-completeness fast, implement backtracking for small graphs, know the Euler-Hamilton distinction cold.