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

A Hamiltonian Cycle is a Hamiltonian Path whose final vertex connects back to the starting vertex, creating a closed cycle.

These concepts are fundamental in graph theory and appear in routing, sequencing, puzzles, combinatorial optimization, and as the structural basis of the Travelling Salesman Problem.

Hamiltonian Path

A valid Hamiltonian Path must:

• visit every vertex,
• visit each vertex exactly once,
• follow valid edges between consecutive vertices,
• not necessarily return to the start.

For example:

A → B → C → D

is Hamiltonian if the graph contains all required edges and these are all the vertices.

Hamiltonian Cycle

A Hamiltonian Cycle adds one more requirement:

last vertex → starting vertex

For example:

A → B → C → D → A

Hamiltonian vs Eulerian

This is one of the most important distinctions in graph algorithms.

Hamiltonian problems focus on vertices:

visit every vertex exactly once

Eulerian problems focus on edges:

use every edge exactly once

A Hamiltonian solution may ignore many graph edges.

An Eulerian solution must include all edges.

Hamiltonian Cycle vs TSP

Hamiltonian Cycle asks:

Does a cycle exist that visits every vertex exactly once?

TSP asks:

Among all such cycles, which one has minimum total cost?

So TSP can be viewed as a weighted optimization version of Hamiltonian Cycle.

Hamiltonian Path vs Shortest Path

Shortest-path algorithms such as Dijkstra optimize travel between selected endpoints.

Hamiltonian Path instead asks for a valid ordering that covers all vertices exactly once.

These are fundamentally different objectives.

Why backtracking is useful

A normal DFS can traverse a graph, but it does not automatically enforce a globally valid one-time ordering of all vertices.

Backtracking explores a candidate choice, continues recursively, and reverses the choice if it creates a dead end.

The pattern is:

1. choose,
2. recurse,
3. detect failure,
4. undo,
5. try another choice.

JavaScript: Hamiltonian Path

function findHamiltonianPath(graph) {
  const nodes = Object.keys(graph);

  function search(current, path, used) {
    if (path.length === nodes.length) {
      return [...path];
    }

    for (const next of graph[current] ?? []) {
      if (used.has(next)) continue;

      used.add(next);
      path.push(next);

      const result = search(next, path, used);

      if (result) return result;

      path.pop();
      used.delete(next);
    }

    return null;
  }

  for (const start of nodes) {
    const result = search(
      start,
      [start],
      new Set([start])
    );

    if (result) return result;
  }

  return null;
}

JavaScript: Hamiltonian Cycle

function findHamiltonianCycle(graph) {
  const nodes = Object.keys(graph);

  function search(start, current, path, used) {
    if (path.length === nodes.length) {
      if ((graph[current] ?? []).includes(start)) {
        return [...path, start];
      }

      return null;
    }

    for (const next of graph[current] ?? []) {
      if (used.has(next)) continue;

      used.add(next);
      path.push(next);

      const result = search(
        start,
        next,
        path,
        used
      );

      if (result) return result;

      path.pop();
      used.delete(next);
    }

    return null;
  }

  for (const start of nodes) {
    const result = search(
      start,
      start,
      [start],
      new Set([start])
    );

    if (result) return result;
  }

  return null;
}

Step-by-step example

Suppose:

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

Starting at A:

[A]

Try B:

[A, B]

Then C:

[A, B, C]

Then D:

[A, B, C, D]

All vertices have been used, so this is a Hamiltonian Path.

For a Hamiltonian Cycle, we must additionally check whether:

D → A

exists.

If not, the algorithm backtracks and tries another ordering.

Complexity

Naive backtracking may explore a factorial number of vertex orders.

Worst-case behavior is roughly:

O(V!)

The direct recursion stack, current path, and visited set usually require approximately:

O(V)

space.

NP-Completeness

The decision versions of Hamiltonian Path and Hamiltonian Cycle are classic NP-Complete problems.

A proposed solution can be verified efficiently, but no general polynomial-time exact algorithm is known for arbitrary graphs.

Bitmask Dynamic Programming

For small or medium graphs, a subset-DP formulation can improve on factorial search.

A state such as:

dp[mask][v]

can represent whether there exists a path that visits exactly the vertices in mask and ends at v.

A transition from u to an unused neighbor v is:

dp[mask | (1 << v)][v] = true

when:

dp[mask][u] = true

and edge u → v exists.

The complexity is typically around:

O(V² × 2^V)

which is still exponential but much better than factorial growth.

Directed and undirected graphs

Hamiltonian problems exist in both settings.

In an undirected graph:

A -- B

allows travel both ways.

In a directed graph:

A → B

only the specified direction is valid.

All path ordering must respect edge direction.

Useful sufficient conditions

Unlike Eulerian paths, Hamiltonian paths do not have a simple general degree rule.

However, results such as Dirac's theorem provide sufficient conditions.

For a simple graph with n ≥ 3, if every vertex has degree at least:

n / 2

then the graph has a Hamiltonian Cycle.

This condition is sufficient, not necessary.

Real-world applications

Visit sequencing

A system may need an order that visits every required location once without repetition.

Route sequencing

If the main constraint is "visit every required node exactly once," the Hamiltonian model can be a useful abstraction.

Graph puzzles

Many puzzles ask the player to pass through every point or cell exactly once.

Structural basis of TSP

TSP adds weights and optimization to the Hamiltonian Cycle structure.

Task sequencing

If tasks are vertices and legal transitions are edges, finding a sequence that uses every task exactly once can resemble Hamiltonian Path.

Bioinformatics

Some historical and theoretical sequence-assembly formulations relate to Hamiltonian paths, although Eulerian formulations are often more practical in modern assembly models.

Important edge cases

• a one-vertex graph,
• disconnected graphs,
• isolated vertices,
• directed edges,
• low-degree vertices,
• graphs where a Hamiltonian Path exists but no Hamiltonian Cycle exists.

Improving backtracking

Practical search can be improved with:

• pruning impossible states,
• trying constrained vertices first,
• memoization,
• bitmask state encoding,
• problem-specific ordering heuristics.

Comparison table

| Problem | Exactly once | Return to start | Optimization | |---|---|---|---| | Hamiltonian Path | Vertex | No | No | | Hamiltonian Cycle | Vertex | Yes | No | | Eulerian Path | Edge | No | No | | Eulerian Cycle | Edge | Yes | No | | TSP | Vertex | Yes | Minimum cost |

When should you use it?

Use Hamiltonian Path or Cycle when every vertex must be used exactly once and the main goal is feasibility or construction of such an ordering.

When is it not a good fit?

Use Eulerian algorithms if every edge must be used.

Use BFS or DFS if you only need general graph traversal.

Use Dijkstra or A* for shortest paths.

Use TSP or another optimization model when the cheapest valid tour is required.

Summary

Hamiltonian Path visits every vertex exactly once.

Hamiltonian Cycle additionally returns to the starting vertex.

The most important conceptual distinction is that Hamiltonian problems are vertex-based, while Eulerian problems are edge-based.

Naive backtracking can require roughly O(V!) time. Bitmask dynamic programming can reduce this to around O(V²2^V), but the problem remains exponential in general.

The key engineering skill is recognizing whether a real problem is Hamiltonian, Eulerian, shortest-path, or an optimization problem such as TSP.