Skip to content
Free public beta until December 4, 2026: every course is open, no card needed. After that, the first chapter of each course stays free and full access is a one-time $39 ($19 for up to 100 founding members chosen for helpful feedback). Your progress is kept. How the beta works

Recipe

Search for a Hamiltonian path or cycle

Use when: you're given a small graph and asked to find a Hamiltonian path or Hamiltonian cycle, or to show none exists

Goal: either a full vertex order proving one exists, or confirmation that every branch of the search dead-ends

Taught in Hamiltonian paths and cycles

Quick recipe

  1. Extend greedily to an unvisited neighbor
  2. Back up when every neighbor is already visited
  3. Check whether the path closes into a cycle
  1. 1

    Pick a starting vertex, then repeatedly move to any neighbor that hasn't been visited yet, building the path up one vertex at a time.

    Example

    Take the graph with edges \{a,b\},\{a,e\},\{b,c\},\{b,e\},\{c,d\}. Starting at a, go to b (an edge exists), then to c, then to d.

    Why: this is the only way to build a sequence that visits every vertex exactly once. Guessing a full order up front and checking it afterward wastes more effort than extending one honest step at a time.

  2. 2

    If the current vertex has no unvisited neighbor left, undo the most recent step and try a different neighbor from further back, instead of giving up immediately.

    Example

    After a \to b \to c \to d, vertex d's only neighbor is c, which is already visited, and e was never reached. Undo back to b and try its other unvisited neighbor: a \to b \to e also dead-ends at once, since e's only neighbors, a and b, are both already visited. Undo all the way back to a and try its other neighbor instead: a \to e \to b \to c \to d visits every vertex, with each consecutive pair a real edge.

    • the greedy extension reaches every vertex with no dead end — a Hamiltonian path is found; continue to Step 3.
    • every neighbor from the current vertex leads to a dead end — back up one more level and try the next untried neighbor there.

    Why: a real Hamiltonian path can sit on a branch a first greedy guess completely misses, so ruling one out takes exhausting every alternative, not just the first attempt.

  3. 3

    Look for an edge directly connecting the path's last vertex back to its first vertex; if one exists, the path plus that edge is a Hamiltonian cycle.

    Example

    The path a \to e \to b \to c \to d ends at d and started at a. Is \{d,a\} an edge of the graph? No -- d's only edge in the whole graph goes to c.

    • an edge from the last vertex back to the first exists — close it and report a Hamiltonian cycle.
    • no such edge exists — the graph still has a Hamiltonian path, just not a Hamiltonian cycle.

    ⚡ Shortcut

    A vertex of degree 1 can never sit on any Hamiltonian cycle, since a cycle needs two distinct edges at every vertex it passes through. Here d has degree 1, so no Hamiltonian cycle was ever possible, no matter how the path was ordered. Checking degrees first can rule out a cycle before spending any time trying to close one.

    Why: a Hamiltonian cycle is, by definition, a Hamiltonian path with one extra edge closing it back to the start, so that specific edge either exists or it doesn't.

Common mistakes

  • Giving up after one greedy attempt dead-ends instead of backtracking to try a different branch.
  • Assuming a path that ignores most of the graph's edges must be wrong -- a Hamiltonian path only has to account for every vertex, never every edge.
  • Trying to close a cycle through a vertex of degree 1, which can never work.
  • Forgetting to check that every consecutive pair in a proposed order is an actual edge, not just a pair of vertices that both happen to be in the graph.