Hamiltonian path: visit every vertex once

Taking the road from A to C looks harmless until the next step ends at B. Both of B’s neighbours have already been visited, and D is still missing. The solver must undo an earlier choice, not revisit a town or pretend the partial route is complete.

Count vertices, not edges#

The illustrative graph has four edges: A–B, B–C, C–A and C–D. A valid Hamiltonian path is A → B → C → D. It visits every vertex once but does not use A–C.

An Eulerian path on this same graph could be D → C → A → B → C. That route covers every edge but repeats C, so it is not Hamiltonian. The rule you count is what changes the problem.

Before trying it, predict what will happen after A → C → B. Choose those vertices in the workbench: D is still unvisited, but B has no unvisited neighbour. Undo B and C, then choose B, C and D to complete the route. The unused edge A–C does not invalidate the answer.

Build a route that visits each vertex once

Illustrative example on the triangle-with-tail graph: start at A, then choose C and B. Can you still reach D without visiting a vertex twice?

Follow an edge between each pair of vertices. Visit every vertex once; leaving some edges unused is allowed.

Graph example Tail graph Star Next vertex (or starting vertex) ABCD

Add vertex Undo last vertex Reset route

Changing the route requires JavaScript. The graph and worked example remain available without it.

Connections in this graph

• A: B, C
• B: A, C
• C: A, B, D
• D: C

Current route

Not started

Visited vertices 0 / 4

None

Unvisited vertices

A, B, C, D

Used edges 0 / 4

None

Unused edges

A–B, A–C, B–C, C–D

Available next vertices

A, B, C, D

Choose a starting vertex. The route must visit all four vertices once; it may leave edges unused.

Triangle-with-tail example and failed choice

A → C → B gets stuck with D unvisited. Undo B and C to return to A, then choose B, C and D. A → B → C → D visits every vertex once and leaves A–C unused.

The route D → C → A → B → C uses all four edges, but repeats C. It is an Eulerian path on the triangle-with-tail graph, not a Hamiltonian path.

This workbench checks your chosen route on two small, simple undirected graphs. It does not search all routes, minimise travel cost, or model directed edges, parallel edges or self-loops. Getting stuck describes this route, not every possible route.

One stuck choice does not show that the graph has no Hamiltonian path. The workbench lets you build and undo a route; it does not search every possibility for you. Its two maps are small, simple undirected graphs, with no weights, parallel edges or self-loops.

Undo a choice that gets stuck#

A direct search maintains a candidate path and the set of vertices already visited. It tries an unvisited neighbour, adds it to both, and continues. A failed attempt removes that vertex from both before trying another neighbour. Undoing a choice in this way is called backtracking.

For the four-edge graph, one possible search begins like this:

Candidate	What happens next
A → C → B	B has no unvisited neighbour; D is missing. Undo B.
A → C → D	D has no unvisited neighbour; B is missing. Undo D, then C.
A → B → C → D	All four vertices appear once. Return this path.

For a counterexample, select the star map in the workbench. B, C and D each connect only to A. Each of those three leaves would have to be an endpoint of a Hamiltonian path: passing through a leaf would require using A again. A path has only two endpoints, so this particular map has no Hamiltonian path. That argument rules out every route; a failed manual attempt alone would not.

The following Python function tries every possible start. Each neighbour must also be a key in graph. For an undirected graph, list each connection in both directions. The order of neighbours controls which valid answer is found first, not whether a route exists.

def hamiltonian_path(graph: dict[str, list[str]]) -> list[str] | None:
    if any(v not in graph for neighbours in graph.values() for v in neighbours):
        raise ValueError("every neighbour must be a graph key")
    if not graph:
        return []

    def search(path: list[str], seen: set[str]) -> list[str] | None:
        if len(path) == len(graph):
            return path.copy()
        for next_vertex in graph[path[-1]]:
            if next_vertex not in seen:
                seen.add(next_vertex)
                path.append(next_vertex)
                found = search(path, seen)
                if found is not None:
                    return found
                path.pop()
                seen.remove(next_vertex)
        return None

    for start in graph:
        found = search([start], {start})
        if found is not None:
            return found
    return None

This is a small-graph teaching implementation. Searching possible visit orders can grow factorially with the number of vertices. Its path, visited set and recursive calls need space proportional to the number of vertices, apart from the input graph. Deep inputs can also hit Python’s recursion limit. The recursion guide shows how those nested calls occupy the call stack.

Do not confuse a complete visit with a cheapest route#

A Hamiltonian cycle needs a final edge back to the start. In our graph, D has only one neighbour. Visiting D and then leaving it to complete a cycle would require C twice, so no such cycle exists. A Hamiltonian path nevertheless exists.

Finding any valid path does not choose a cheapest one. With weighted edges, two Hamiltonian paths can have different costs. Asking for the cheapest tour that also returns to its start leads to a travelling-salesperson problem. Asking only for a cheapest route from one start to a destination is different again; for nonnegative weights, use a shortest-path method such as Dijkstra.

Write down what must be covered and what may be repeated before selecting an algorithm. “Visit every vertex once” is a requirement, not another name for “take a short route”.

Questions people also ask

2 QUESTIONS

▸ Does visiting all vertices make a Hamiltonian cycle?

No. A cycle also needs an edge from the last vertex back to the start. In the example, D has only the edge to C, so no Hamiltonian cycle exists.

▸ What does the example function return when no route exists?

It returns None after trying every starting vertex. For an empty graph it returns an empty list by convention; for a graph with one vertex it returns that vertex.