Fact-checked by Grok 2 weeks ago

Hamiltonian path

A Hamiltonian path in an undirected graph is a path that visits each vertex exactly once.^[1] This concept, central to graph theory, distinguishes itself from an Eulerian path, which visits every edge exactly once but may revisit vertices.^[1] The term originates from the work of Irish mathematician Sir William Rowan Hamilton, who in 1857 devised the Icosian game—a puzzle requiring players to trace a cycle visiting each of the 20 vertices of a dodecahedron exactly once, effectively seeking a Hamiltonian cycle on its graph.^[2] Hamilton's invention popularized the idea, though the broader study of such paths and cycles emerged later in combinatorial graph theory during the 20th century.^[2] Determining whether a given graph contains a Hamiltonian path is a classic decision problem in computational complexity, proven to be NP-complete for directed graphs via reduction from the 3-SAT problem.^[3] For undirected graphs, the problem is also NP-complete, as established through polynomial-time reductions from known NP-complete problems like the Hamiltonian cycle.^[4] This intractability underscores its foundational role in theoretical computer science, where no efficient algorithm exists for arbitrary graphs unless P=NP.^[3] Hamiltonian paths find applications in optimization problems, such as approximating solutions to the traveling salesman problem, where they form the basis for finding near-optimal tours in logistics and network routing.^[5] They also appear in scheduling tasks on processors without repetition, genome sequencing assembly, and designing efficient circuits in VLSI technology.^[6] Related structures include Hamiltonian cycles (closed paths) and Dirac's theorem, which provides a sufficient condition for the existence of a Hamiltonian cycle in graphs with sufficiently high minimum degree.^[7]

Basic Concepts

Definition

In graph theory, a graph consists of a set of vertices V and a set of edges E connecting pairs of vertices, where a path is a sequence of distinct vertices connected by edges in the given order.^[8] A Hamiltonian path in an undirected graph G = (V, E) is a path that visits each vertex in V exactly once.^[8] Formally, it is a sequence of vertices v_1, v_2, \dots, v_n such that \{v_1, v_2, \dots, v_n\} = V and there exists an edge \{v_i, v_{i+1}\} \in E for each i = 1, 2, \dots, n-1, where n = |V|.^[9] This definition extends to directed graphs, where edges are ordered pairs (arcs). A directed Hamiltonian path in a directed graph G = (V, E) is a sequence v_1 \to v_2 \to \dots \to v_n such that \{v_1, v_2, \dots, v_n\} = V and there exists a directed edge (v_i, v_{i+1}) \in E for each i = 1, 2, \dots, n-1.^[10] Unlike trails, which may revisit vertices but not edges, a Hamiltonian path is a simple path with no repeated vertices, emphasizing complete vertex coverage without repetition.^[11] A Hamiltonian cycle, by contrast, is a closed Hamiltonian path that returns to the starting vertex via an additional edge.^[9] This distinguishes Hamiltonian paths from Eulerian paths, which traverse each edge exactly once but may revisit vertices.^[12] A Hamiltonian cycle is a closed path in a graph that visits each vertex exactly once and returns to the starting vertex, equivalent to a Hamiltonian path whose endpoints are connected by an edge.^[2] This structure differs from a Hamiltonian path by requiring closure, which imposes stricter connectivity conditions on the graph. A graph is termed Hamiltonian if it contains at least one Hamiltonian cycle.^[13] Importantly, while the primary focus here is on Hamiltonian paths, a graph may possess a Hamiltonian path without containing a Hamiltonian cycle, as the open path does not necessitate an edge between its endpoints. A Hamiltonian path corresponds to a spanning subgraph of the original graph that is isomorphic to the path graph P_n, where n is the number of vertices. More specifically, if the Hamiltonian path is induced, the subgraph induced by its vertices contains only the edges of the path itself, with no additional edges (chords) between non-consecutive vertices. Induced Hamiltonian paths represent a variant where the absence of such chords ensures the path is chordless in the induced subgraph. The longest path problem generalizes the concept of a Hamiltonian path by seeking a simple path of maximum length in a graph; a Hamiltonian path achieves this maximum if it exists, spanning all vertices.^[14] The terminology "Hamiltonian" derives from Sir William Rowan Hamilton's invention of the Icosian game in 1857, a puzzle requiring the identification of a Hamiltonian cycle along the edges of a dodecahedral graph.^[15]

Examples

Elementary Graphs

The path graph P_n, consisting of n vertices connected in a linear chain by n-1 edges, is itself a Hamiltonian path, providing the trivial case where the graph structure directly realizes the definition.^[16] For small n, such as n=3, P_3 can be visualized as three vertices v_1, v_2, v_3 with edges v_1-v_2 and v_2-v_3, traversing all vertices exactly once from v_1 to v_3. This example illustrates the basic linear connectivity without branches or cycles.^[17] In contrast, the complete graph K_n, where every pair of distinct vertices is connected by a unique edge, admits Hamiltonian paths for all n \geq 2. Any permutation of the n vertices defines such a path, as all required edges exist. For undirected K_n, the number of distinct Hamiltonian paths is \frac{n!}{2}, since each path is counted twice in the n! permutations—once in each direction.^[1] A simple case is K_3, a triangle with vertices a, b, c and edges a-b, b-c, c-a; the three Hamiltonian paths are a-b-c, a-c-b, and b-a-c (with reverses identical in the undirected sense). For n=4, expanding to vertices a, b, c, d, paths like a-b-c-d highlight the abundance of options due to full connectivity.^[18] The cycle graph C_n, formed by connecting n vertices in a single loop, contains a Hamiltonian path obtained by removing any one edge, yielding a path graph P_n. This contrasts with the cycle's closed structure, as the path version opens the loop while preserving vertex coverage. For n=4, C_4 is a square with vertices w, x, y, z and edges w-x, x-y, y-z, z-w; removing z-w produces the path w-x-y-z. Such examples demonstrate how minor modifications to cyclic graphs produce Hamiltonian paths.^[19] As a simple counterexample, the star graph K_{1,3}, consisting of one central vertex connected to three leaves, lacks a Hamiltonian path. Any path starting at a leaf can visit the center and one other leaf but cannot reach the third leaf without revisiting the center.^[20] This illustrates how branching structures prevent full vertex traversal in a single path.

Graph Families

In trees, a Hamiltonian path exists if and only if the tree has exactly two leaves, in which case the tree itself is a path graph.^[21] Path graphs are a special case of caterpillar trees, which are trees in which removing all leaves yields a path (the spine), though only the paths among them possess a full Hamiltonian path visiting every vertex.^[22] Bipartite graphs admit Hamiltonian paths under specific balance conditions on their partitions. In a complete bipartite graph K_{m,n}, a Hamiltonian path exists if and only if |m - n| \leq 1, as the path must alternate between the two partitions, allowing at most one extra vertex in the starting partition.^[23] For example, in K_{3,3}, a path can traverse all vertices by alternating sides, but in K_{3,2}, it covers all while ending in the larger set, whereas K_{4,2} lacks such a path due to imbalance. Tournaments, which are directed complete graphs, always contain a Hamiltonian path. This is guaranteed by Rédei's theorem, which states that every tournament on n vertices has at least one directed Hamiltonian path visiting all vertices in sequence.^[24] The theorem, originally proved in 1934, highlights the strong ordering properties inherent in tournaments. Grid graphs, formed by the Cartesian product of two paths (an m \times n lattice), always possess a Hamiltonian path regardless of the dimensions m and n (assuming m, n \geq 1). A simple construction snakes through the rows or columns in alternating directions to visit every vertex exactly once.^[25] Unlike Hamiltonian cycles, which fail to exist when both m and n are odd due to bipartition parity issues, paths are unaffected by this restriction.^[26] Hypotraceable graphs provide an extremal example regarding Hamiltonian paths, defined as non-traceable graphs (lacking a Hamiltonian path) such that the removal of any single vertex yields a traceable subgraph (with a Hamiltonian path).^[27] These graphs, analogous to hypohamiltonian graphs for cycles, demonstrate the delicate boundary between having and lacking such paths, with the smallest known examples having 34 vertices.^[27]

Properties

Structural Characteristics

A Hamiltonian path in a graph G = (V, E) with |V| = n is defined as a path consisting of exactly n-1 edges that visits each vertex precisely once, thereby spanning the entire vertex set V. This length ensures that no vertex is omitted or revisited, distinguishing it from shorter paths or cycles. The existence of such a path implies that the graph G is connected, since the path itself forms a connected spanning subgraph that links all vertices through consecutive adjacencies. However, this connectivity is not necessarily 2-connected; graphs like trees, which contain Hamiltonian paths but possess cut vertices, illustrate that bridges or articulation points may still exist. In the subgraph induced by the Hamiltonian path, the two endpoint vertices have degree 1, while all internal vertices have degree 2, reflecting the linear structure of the path.^[28] A Hamiltonian path can be formally represented as a sequence of distinct vertices v_1, v_2, \dots, v_n such that (v_i, v_{i+1}) \in E for all i = 1, 2, \dots, n-1. This sequential form highlights the path's dependence on the graph's adjacency relations without invoking broader matrix representations. Regarding uniqueness, certain graphs possess exactly one Hamiltonian path; for instance, the path graph P_n has a unique such path consisting of its own edges. In contrast, denser graphs like the complete graph K_n exhibit a multiplicity of Hamiltonian paths, underscoring how structural density influences the variety of spanning traversals.^[28]

Degree and Connectivity Conditions

A graph must be connected to admit a Hamiltonian path, as any path spanning all vertices requires the graph to be in a single component. Unlike the case for Hamiltonian cycles, which necessitate 2-connectivity to avoid articulation points that could prevent closing the cycle, 1-connectivity suffices as a necessary condition for Hamiltonian paths. The minimum degree of the graph must be at least 1, ensuring no isolated vertices, since an isolated vertex cannot be visited by a path that includes all other vertices. The graph can have at most two vertices of degree 1, as each such vertex must serve as an endpoint of the Hamiltonian path, and a path has precisely two endpoints; more than two degree-1 vertices would leave at least one unable to be incorporated without violating the degree constraint in the spanning path. A stronger necessary condition involving both degrees and connectivity is that for every nonempty subset S of vertices, the number of components in G − S is at most |S| + 1. This limits how fragmented the graph can become upon vertex removal and is a generalization attributed to Chvátal's work on graph toughness properties for Hamiltonian structures.00141-1) Regarding the degree sequence, a basic necessary condition is that the sorted degrees d_1 \leq d_2 \leq \dots \leq d_n must allow for a connected realization with minimum degree at least 1 and at most two degrees equal to 1, consistent with the handshaking lemma that the sum of degrees is even. More advanced analysis shows that sequences failing certain thresholds, such as those where d_i < i for many i without compensating high degrees at the end, cannot guarantee a Hamiltonian path in all realizations, though they are not strictly necessary for existence in a specific graph.^[29] Hypohamiltonian graphs provide counterexamples illustrating that these conditions are far from sufficient; such graphs are non-Hamiltonian but become Hamiltonian upon removal of any single vertex, serving as near-misses where degree and connectivity conditions hold yet no spanning cycle exists (with analogous hypotraceable graphs for paths exhibiting similar behavior for spanning paths).90071-8)

Sufficient Conditions and Theorems

Dirac's Theorem

Dirac's theorem states that if G is a simple graph with n \geq 3 vertices and minimum degree \delta(G) \geq n/2, then G contains a Hamiltonian cycle.^[30] This result was established by Gabriel Dirac in his 1952 paper "Some Theorems on Abstract Graphs," marking a foundational contribution to sufficient conditions for Hamiltonicity in graph theory.^[30] The proof relies on a longest path argument. Assume G has no Hamiltonian cycle; consider a longest path P = v_1 v_2 \dots v_k in G, with k < n. The endpoints v_1 and v_k cannot share neighbors on P except possibly each other, but the high minimum degree ensures that v_1 has at least n/2 - (k-2) neighbors outside P, and similarly for v_k. For k \geq n/2 + 1, this leads to a neighbor of v_1 adjacent to v_k or an extension of P, contradicting maximality and yielding a cycle or longer path. Iterating this process forces a Hamiltonian cycle.^[30] Since any graph with a Hamiltonian cycle also admits a Hamiltonian path (by removing one edge from the cycle), Dirac's theorem immediately implies the existence of a Hamiltonian path in such graphs. More directly, the condition guarantees a path by the same reasoning, as the proof constructs paths extendable to cycles but applies analogously to path existence.^[30] The theorem is sharp, as demonstrated by the complete bipartite graph K_{\lfloor n/2 \rfloor - 1, \lceil n/2 \rceil + 1}, which has minimum degree \lfloor n/2 \rfloor - 1 < n/2 and no Hamiltonian cycle due to unequal part sizes preventing alternation in a cycle covering all vertices.^[31] Examples of graphs satisfying the condition include complete graphs K_n, where \delta(G) = n-1 > n/2 for n \geq 3, ensuring Hamiltonicity. Cycle graphs C_n satisfy the degree condition only for small n \leq 4 (e.g., C_3 and C_4), where \delta = 2 \geq n/2, and indeed possess Hamiltonian cycles.^[30]

Ore's Theorem

Ore's theorem provides a sufficient condition for the existence of a Hamiltonian cycle in a simple undirected graph, generalizing Dirac's theorem by considering pairwise degree sums rather than a uniform minimum degree. Specifically, for a graph G with n \geq 3 vertices, if \deg(u) + \deg(v) \geq n for every pair of non-adjacent vertices u and v in G, then G contains a Hamiltonian cycle. This condition was stated and proved by Norwegian mathematician Øystein Ore in a concise note published in 1960.^[32] The theorem implies Dirac's theorem, as a minimum degree \delta(G) \geq n/2 ensures that the degree sum of any two non-adjacent vertices is at least n, but Ore's condition can apply to graphs where the minimum degree falls below n/2 while higher-degree vertices compensate for pairs with lower degrees. For instance, the Petersen graph, a well-known non-Hamiltonian graph with 10 vertices and regular degree 3, fails Ore's condition because non-adjacent vertices have degree sum 6, which is less than 10.^[28] The proof of Ore's theorem mirrors the structure of Dirac's proof but leverages the degree sum condition to handle non-uniform degrees. Consider a longest path P = x_0 x_1 \dots x_{k} in G, with endpoints u = x_0 and v = x_k. If u and v are adjacent, P extends to a Hamiltonian cycle. Otherwise, the neighbors of u on P lie in \{x_1, \dots, x_{\deg(u)}\} and the neighbors of v lie in \{x_{k - \deg(v) + 1}, \dots, x_k\}, due to the maximality of P. If these intervals are disjoint, then \deg(u) + \deg(v) \leq k \leq n-1 < n, contradicting the hypothesis. Thus, the intervals overlap at some x_i, implying edges u x_i and v x_i, which either form a longer path or a cycle containing P, again contradicting maximality. This forces a Hamiltonian cycle. Since a Hamiltonian cycle induces a Hamiltonian path by removing one edge, Ore's condition also guarantees the existence of a Hamiltonian path in G. This makes the theorem particularly useful for graphs that satisfy the pairwise sum but not the stricter minimum degree requirement of Dirac's theorem.

Bondy–Chvátal Theorem

The Bondy–Chvátal theorem offers a powerful characterization of Hamiltonian graphs through an iterative closure operation that incorporates and generalizes prior degree-based sufficient conditions for Hamiltonicity. Formulated by J. A. Bondy and V. Chvátal in their 1976 paper, the theorem asserts that a simple undirected graph G of order n \geq 3 is Hamiltonian if and only if its closure G^\sigma is Hamiltonian.^[33] The closure G^\sigma is defined as the graph obtained from G by repeatedly adding an edge between any two non-adjacent vertices u and v whenever \deg(u) + \deg(v) \geq n, continuing this process until no further edges can be added (i.e., the graph stabilizes). This operation is well-defined and results in a unique graph G^\sigma that spans the same vertex set as G, with \deg_{G^\sigma}(u) \geq \deg_G(u) for all vertices u. The construction ensures that G^\sigma satisfies the degree sum condition from Ore's theorem for all non-adjacent pairs, thereby unifying Dirac's minimum degree condition and Ore's pairwise degree sum condition into a single framework. For instance, if G satisfies Dirac's condition (\delta(G) \geq n/2), then G^\sigma = K_n, the complete graph on n vertices, which is Hamiltonian.^[33] The proof of the theorem hinges on two key observations: first, the closure operation preserves Hamiltonicity in both directions—adding edges cannot eliminate an existing Hamiltonian cycle in G, and any Hamiltonian cycle in G^\sigma can be "reconstructed" in G by leveraging the degree conditions to ensure the added edges can be bypassed via alternative paths; second, since the complete graph K_n is Hamiltonian (by ordering the vertices arbitrarily), if G^\sigma = K_n, then G is Hamiltonian. This equivalence allows for practical verification: compute the closure (which can be done in polynomial time) and check if the resulting graph is complete or otherwise known to be Hamiltonian. The theorem thus provides an algorithmic tool for applying Ore-like conditions without directly testing every pair of vertices.^[33] Although primarily stated for Hamiltonian cycles, the closure concept extends to Hamiltonian paths. Specifically, if G^\sigma contains a Hamiltonian cycle, then G contains a Hamiltonian path, as the cycle in the closure implies a spanning path that can be adapted back to the original graph using the preserved connectivity properties. This extension is particularly useful for problems where path existence is required rather than cycle existence, aiding in verification without full cycle detection.^[33]

Hamiltonian Paths in Special Graphs

Planar Graphs

In planar graphs, the study of Hamiltonian paths is intertwined with that of Hamiltonian cycles, since the existence of a cycle immediately implies the existence of a Hamiltonian path by omitting any single edge from the cycle. However, not all planar graphs possess Hamiltonian paths; for instance, a connected planar graph with a vertex of degree greater than or equal to the number of leaves in a star-like structure may fail to have one, as seen in certain trees embedded in the plane. A fundamental property is that every 4-connected planar graph not only has a Hamiltonian cycle but is also Hamiltonian-connected, meaning there exists a Hamiltonian path between any pair of distinct vertices.^[34] The cornerstone results establishing sufficient conditions for Hamiltonicity in planar graphs date back to the early 20th century. In 1931, Hassler Whitney proved that every 4-connected maximal planar graph (i.e., a planar triangulation) admits a Hamiltonian cycle.^[35] This was generalized in 1956 by W.T. Tutte, who showed that every 4-connected planar graph has a Hamiltonian cycle; Tutte's proof relies on constructing a special cycle where each "bridge" (a component of the graph minus the cycle with exactly three attachments to the cycle) satisfies particular attachment conditions to ensure extendability to a full Hamiltonian cycle.^[36] These theorems imply the existence of Hamiltonian paths in such graphs, as any Hamiltonian cycle yields one, and the Hamiltonian-connected property further guarantees paths between specified endpoints. For triangulated planar graphs, which are maximal planar and thus have minimum degree at least 3 for orders greater than or equal to 4, the minimum degree condition δ ≥ 3 is necessary but not always sufficient for Hamiltonicity, though it holds for the 4-connected subclass by Whitney's theorem. In cases involving bridges, Tutte's framework provides a constructive sufficient condition: if a 3-connected planar graph admits a cycle such that every bridge relative to that cycle attaches at exactly three points, then the graph is Hamiltonian.^[36] This approach has been extended in subsequent works to identify additional classes, such as certain near-triangulations, where such cycles exist. Despite these guarantees, not all planar graphs are Hamiltonian, even among highly symmetric subclasses. For example, there exist 3-connected planar triangulations that lack Hamiltonian cycles, serving as counterexamples to weaker connectivity assumptions. A prominent open question is Barnette's conjecture, proposed in 1969, which posits that every 3-connected cubic bipartite planar graph (equivalently, every even-faced 3-connected cubic planar graph) is Hamiltonian; this remains unresolved as of 2025, with no counterexample having fewer than 86 vertices, though verified affirmatively for all such graphs with fewer than 86 vertices.^[37] In August 2025, it was proved that such graphs with all faces of size at most 8 are Hamiltonian.^[38] Computationally, determining the existence of a Hamiltonian path or cycle in a planar graph is NP-complete, even when restricted to cubic 3-connected instances.^[39] However, the planarity constraint allows for more efficient practical algorithms in many cases, particularly for graphs with small embeddings or bounded treewidth, where dynamic programming techniques can solve instances faster than general exponential-time methods, often in practice for graphs up to a few hundred vertices.^[39]

Dirac Graphs and Variants

A Dirac graph is a simple undirected graph on n vertices where the minimum degree δ(G) ≥ n/2. Dirac's theorem establishes that every such graph with n ≥ 3 contains a Hamiltonian cycle, which immediately implies the existence of a Hamiltonian path. This condition ensures Hamiltonicity in high-degree settings, providing a foundational result for understanding Hamiltonian paths in dense graphs. The proof involves constructing a longest path and using the degree condition to close it into a cycle, with the path following as a subgraph. Variants of Dirac graphs include those with minimum degree close to n/2, such as δ(G) = floor(n/2), which represent extremal cases near the threshold for Hamiltonicity. In these variants, the presence of a Hamiltonian path is not always guaranteed, but additional connectivity or closure conditions (as in the Bondy–Chvátal theorem) can ensure it. Hypohamiltonian graphs, which are non-Hamiltonian but become Hamiltonian upon removal of any single vertex, are rare and cannot be Dirac graphs due to the theorem's guarantee; however, examples with relatively high minimum degree exist, such as the 10-vertex Thomassen graph with δ(G) = 3. These variants highlight the sharpness of degree conditions, as increasing the degree beyond certain thresholds eliminates such pathologies. The extremal graph for the minimum degree condition on Hamiltonian paths is the disjoint union of two complete graphs K_{floor(n/2)} and K_{ceil(n/2)}, which has δ(G) = floor(( n-1 )/2 ) and lacks a Hamiltonian path due to disconnection. However, any graph with δ(G) ≥ floor(( n-1 )/2 ) + 1 contains a Hamiltonian path, as the degree condition forces connectivity and allows extension of a longest path to span all vertices—a modification of Dirac's proof technique. This threshold is sharp, as the example shows the bound cannot be lowered without risking non-traceability.^[29] Fan graphs and wheel graphs provide concrete examples of structures that always admit Hamiltonian paths and often satisfy Dirac-like degree conditions for large n. The fan graph F_n, formed by connecting a hub vertex to all vertices of a path on n-1 vertices, has a Hamiltonian path starting at the hub and following the outer path sequentially. The wheel graph W_n, formed by connecting a hub to all vertices of a cycle on n-1 vertices, contains a Hamiltonian cycle (visiting the rim and returning via the hub), yielding a Hamiltonian path from the hub to any rim vertex by removing one rim edge. Both families are Hamiltonian for n ≥ 3, with the hub ensuring high degree and easy path construction. As of 2025, there have been no major theoretical updates to Hamiltonian paths in Dirac graphs, but connections to random graph models remain active. In the Erdős–Rényi random graph G(n, p) with p = 1/2 + ε for fixed ε > 0, the minimum degree exceeds n/2 with high probability, satisfying the Dirac condition and thus containing a Hamiltonian path almost surely. This ties extremal degree conditions to probabilistic guarantees, where the Dirac threshold provides a deterministic regime above the actual Hamiltonicity threshold of roughly (ln n)/ n.

Computational Aspects

Decision Problem Complexity

The decision version of the Hamiltonian path problem, denoted HAMPATH, asks whether a given undirected graph G = (V, E) contains a path that visits each vertex in V exactly once (i.e., a path of length |V| - 1). This problem is in NP, as a proposed path serves as a polynomial-time verifiable certificate: one can check in O(|V| + |E|) time that it includes all vertices exactly once and consists of valid edges. HAMPATH is NP-complete for general graphs.^[4] Richard Karp formalized this for HAMPATH in 1972 by including it among 21 NP-complete problems, reducing from the vertex cover problem via the Hamiltonian cycle problem (HC).^[4] A standard polynomial-time reduction from HC to HAMPATH proceeds as follows: given a graph G for HC, select an arbitrary vertex v and create a new graph G' by replacing v with two vertices v_1 and v_2, connecting all original neighbors of v to both v_1 and v_2, and adding an edge between v_1 and v_2. Then G has a Hamiltonian cycle if and only if G' has a Hamiltonian path from v_1 to v_2. This preserves the structure such that any cycle through v in G "opens" into a path from v_1 to v_2 in G', and vice versa.^[40] In parameterized complexity, HAMPATH is fixed-parameter tractable (FPT) when parameterized by the treewidth tw of the graph, solvable in time $2^{O(tw \log tw)} n^{O(1)} using dynamic programming over a tree decomposition, which exploits the graph's tree-like structure to track partial paths efficiently. However, the problem of finding a path of length at least k (a generalization of HAMPATH for k = |V|) is W^[41]-hard when parameterized by k, indicating no FPT algorithm exists unless FPT = W^[41]. This hardness underscores that parameterizations by solution length do not yield tractability, unlike structural parameters like treewidth. As of 2025, no polynomial-time algorithm is known for HAMPATH on general graphs, maintaining its status as a canonical NP-complete problem with broad implications for approximation and optimization. Quantum approaches, such as the quantum approximate optimization algorithm (QAOA), have been explored for approximating solutions to related Hamiltonian problems, but they do not resolve the exact decision version in polynomial time.^[42]

Algorithms and Solvers

Exact algorithms for determining the existence of a Hamiltonian path in general graphs rely on exponential-time methods due to the problem's NP-completeness. A foundational approach is the dynamic programming technique developed by Held and Karp for the traveling salesman problem (TSP), which can be adapted to the Hamiltonian path problem by computing the shortest (or existence of) path visiting a subset of vertices ending at a specific vertex. The state is defined as a pair (S, v), where S is a subset of vertices and v is the endpoint, with transitions adding a new vertex adjacent to v; this yields a time complexity of O(2^n n^2).^[5] Branch-and-bound methods explore the space of possible paths by building partial solutions and pruning branches that exceed lower bounds on the remaining cost or violate connectivity. These algorithms use relaxations, such as minimum spanning trees or linear programming bounds, to estimate the cost of completing a partial path, enabling efficient search tree reduction for instances up to moderate sizes (n ≈ 50-100 depending on graph density). Performance comparisons show branch-and-bound outperforming exhaustive search on sparse graphs but scaling poorly beyond n=100 without advanced bounding.^[43]^[44] Heuristic methods provide approximate solutions for large instances where exact algorithms are infeasible. The nearest neighbor heuristic starts at an arbitrary vertex and iteratively appends the closest unvisited neighbor, forming a path that can be refined by local improvements like 2-opt swaps; adapted from TSP, it achieves an approximation ratio of O(log n) in metric spaces. Genetic algorithms evolve a population of candidate paths using selection, crossover (e.g., order crossover to preserve partial sequences), and mutation (e.g., inverting subsequences), converging to near-optimal paths on benchmark instances with n up to 1000.^[45]^[46] In special graph classes, polynomial-time algorithms exist. For trees, a linear-time dynamic programming approach computes whether a path covers all vertices by rooting the tree at an arbitrary node and tracking the longest path states in subtrees, starting from leaves and propagating upward; this identifies a Hamiltonian path if the tree satisfies structural conditions like having a spine with pending paths. For tournaments (complete oriented graphs), a Hamiltonian path always exists by Rédei's theorem, and one can be constructed in O(n^2) time by sorting vertices by out-degree and inserting each into the current path at the appropriate position via linear scans.^[47]^[48] Software tools facilitate implementation and solving. The Concorde TSP solver can be adapted for Hamiltonian paths by reformulating the instance as an asymmetric TSP with a dummy vertex to break the cycle requirement, solving instances up to n=10,000 in practice with branch-and-cut techniques. The NetworkX Python library provides an implementation for finding Hamiltonian paths in tournaments using the O(n^2) insertion method, integrated with graph analysis workflows.^[49]^[50] Recent advances (as of 2025) include integer linear programming (ILP) formulations using the Miller-Tucker-Zemlin (MTZ) constraints or subtour elimination, solved efficiently with commercial solvers like Gurobi for instances up to n=200; these leverage cutting planes and presolving but offer no asymptotic breakthrough for the general case, remaining exponential in worst-case complexity.^[51]

Advanced Topics

Counting and Polynomials

Counting the number of Hamiltonian paths in a graph is a fundamental enumerative problem in graph theory, with applications across combinatorics and related fields. Unlike the decision problem of existence, which is NP-complete, counting is #P-complete even for restricted classes such as planar graphs of maximum degree 3. This hardness holds under parsimonious reductions, implying that exact counts cannot be computed in polynomial time unless P = NP. Recent algebraic methods, including evaluations of specialized polynomials and fingerprinting techniques, provide computational bounds and approximations, but exact counting remains intractable for general graphs as of 2025. A key example of exact counting occurs in the complete graph K_n, where every permutation of vertices corresponds to a path, accounting for directionality. The number of undirected Hamiltonian paths is precisely \frac{n!}{2}, as there are n! directed paths and each undirected path is counted twice. In symmetric graphs, such as those with nontrivial automorphism groups, the count adjusts by a factor related to the group order; for instance, in vertex-transitive graphs, the number of Hamiltonian paths between fixed endpoints is \frac{(n-1)!}{|\Aut(G)|} times the automorphism-stabilizing factor for the pair. For lattice graphs, like rectangular grids, the transfer matrix method enables systematic enumeration of Hamiltonian paths by building configurations row-by-row or column-by-column, tracking connectivity states. This approach yields exact counts for small dimensions, such as m \times n grids with fixed m, and has been implemented to compute numbers up to thousands of paths in feasible time. These methods are particularly effective for strip-like lattices, where the state space grows exponentially with width but linearly with length. In statistical mechanics, counting Hamiltonian paths models self-avoiding walks on lattices, which approximate polymer configurations under excluded volume effects. The number of such walks of length n-1 equals the number of Hamiltonian paths on n sites, with asymptotic growth governed by the connective constant \mu, estimated via series analysis or Monte Carlo methods. Inclusion-exclusion principles provide asymptotic bounds and closed-form expressions in special cases, such as multipartite complete graphs, by subtracting overcounts of invalid paths or cycles.

Generalizations and Variants

A directed Hamiltonian path is a path in a directed graph that visits each vertex exactly once, following the direction of edges. In tournaments—complete directed graphs where every pair of vertices has exactly one directed edge—every such graph contains at least one directed Hamiltonian path, a result originally proved by Rédei in 1934. This property holds for all tournaments, not just strong ones (where every pair of vertices is mutually reachable), though strong tournaments additionally guarantee the existence of a directed Hamiltonian cycle by Camion's theorem. However, the general directed Hamiltonian path problem remains NP-complete, even when restricted to directed graphs, as shown by a polynomial-time reduction from the 3-SAT problem.^[52]^[3] In weighted graphs, the shortest Hamiltonian path problem seeks a minimum-weight path visiting each vertex exactly once and is a close variant of the traveling salesman problem (TSP). For metric graphs—where edge weights satisfy the triangle inequality—this problem admits approximation algorithms; for instance, a 3/2-approximation can be achieved using extensions of Christofides' algorithm adapted for paths rather than cycles. In the Euclidean setting, where vertices are points in Euclidean space and weights are distances, polynomial-time approximation schemes (PTAS) exist that approximate the optimum to any desired factor (1+ε) in polynomial time. These results highlight the tractability of approximate solutions despite the NP-hardness of the exact problem.^[53] Labeled or colored variants extend the concept to edge-colored graphs, where a rainbow Hamiltonian path requires all edges to have distinct colors. In 1990, Geoffrey Hahn conjectured that every properly edge-colored complete graph on n \geq 3 vertices contains a rainbow Hamiltonian path, but this was disproved by Maamoun and Meyniel in 1984 for even n \geq 4. Counterexamples also exist for non-proper colorings. Nonetheless, almost all optimally edge-colored complete graphs admit a rainbow Hamiltonian path, as shown probabilistically for large n. In random edge-colored graphs, rainbow Hamiltonian paths emerge with high probability when the coloring uses sufficiently many colors relative to the graph's density. These variants find use in combinatorial design and fault-tolerant network routing.^[54]^[55] Key open problems in Hamiltonian paths include the P versus NP question: since the decision problem is NP-complete, a polynomial-time algorithm for it would imply P = NP, resolving one of the Clay Millennium Prize Problems. Another concerns Hamiltonicity in random graphs G(n,p), where the threshold probability for the existence of a Hamiltonian path (or cycle) is asymptotically (log n)/n; below this, such paths vanish with high probability, while above it, they appear almost surely. These thresholds inform probabilistic methods in graph theory and algorithm design.^[56]^[57] Applications of Hamiltonian paths span bioinformatics and engineering. In DNA sequencing, overlap graphs model fragments as vertices with edges for overlaps; finding a Hamiltonian path reconstructs the original sequence, though practical assemblies often use path covers (disjoint paths covering all vertices) due to sequencing errors and incompleteness. In robotics, Hamiltonian paths optimize tour planning for tasks like inspection or delivery, ensuring efficient traversal of waypoints while avoiding redundancy; heuristic solvers adapt TSP approximations for real-time path generation in dynamic environments.^[58]^[59] Recent advances as of 2025 explore quantum algorithms for approximate Hamiltonian paths, particularly via the quantum approximate optimization algorithm (QAOA). QAOA encodes the problem as a quadratic unconstrained binary optimization over an Ising Hamiltonian and iteratively optimizes variational parameters to find near-optimal paths; simulations show it outperforms classical heuristics for small instances in routing applications, though scaling to large graphs remains limited by noise in current quantum hardware, with no polynomial-time exact resolution in sight.^[42]

References

[1]
Hamiltonian Path -- from Wolfram MathWorld
A Hamiltonian path, also called a Hamilton path, is a graph path between two vertices of a graph that visits each vertex exactly once.
[2]
Hamiltonian Cycle -- from Wolfram MathWorld
A graph possessing exactly one Hamiltonian cycle is known as a uniquely Hamiltonian graph. In general, the problem of finding a Hamiltonian cycle is NP-complete ...
[3]
[PDF] Hamiltonian Path is NP-Complete
Mar 5, 2020 · We will prove that the problem D-HAM-PATH of determining if a directed graph has an Hamiltonian path from s to t is NP-Complete. Theorem 1. D- ...
[4]
[PDF] REDUCIBILITY AMONG COMBINATORIAL PROBLEMS
REDUCIBILITY AMONG COMBINATORIAL PROBLEMS. 87 elements of other countable domains. It is a reasonable working hypothesis, championed originally by Jack ...
[5]
[PDF] 1 Hamiltonian Path - People | MIT CSAIL
Nov 2, 2020 · In this lecture and the next, we will introduce a number of algorithmic techniques used in exponential-time and FPT algorithms, through the lens ...Missing: applications | Show results with:applications
[6]
[PDF] Lecture 19: Applications of DFS - CS@Columbia
Nov 30, 2015 · Hamiltonian Path/Cycle is much harder! • No polynomial time solution (i.e. O(Nk) ) is known. No hamiltonian path.
[7]
[PDF] GRAPH THEORY WITH APPLICATIONS
A path that contains every vertex of G is called a Hamilton path of G; similarly, a Hamilton. cycle of. G is a cycle that contains every vertex of G. Such paths ...
[8]
[PDF] Note 13 - People @EECS
A Hamiltonian path in an undirected graph G = (V,E) is a path that goes through every vertex exactly once. A Hamiltonian cycle (or Hamiltonian tour) is a cycle ...
[9]
[PDF] Graph Theory and Complex Networks: An Introduction Chapter 04
Definition. A Hamilton path of a connected graph G is a path that contains every vertex of G. A Hamilton cycle is a cycle containing every vertex of G. G is ...
[10]
[PDF] Hamiltonicity in Cayley graphs and digraphs of finite abelian groups
Similarly, a directed graph is called Hamiltonian if there is a path that visits every vertex in the graph exactly once while observing edge directions, and ...
[11]
[PDF] (Re)Introduction to Graphs and Some Algorithms
A Hamiltonian Path is a path that visits every vertex in a graph exactly once. • An Eulerian Path is a path that visits every edge in a graph exactly once.
[12]
All You Need to Know about Graph Theory
A Hamiltonian path in a graph is a path that visits each vertex of the graph exactly once. A Eulerian path in a graph is a path that visits each edge of the ...
[13]
Hamiltonian Graph -- from Wolfram MathWorld
A Hamiltonian graph, also called a Hamilton graph, is a graph possessing a Hamiltonian cycle. A graph that is not Hamiltonian is said to be nonhamiltonian.
[14]
QUBO formulations of the longest path problem - ScienceDirect.com
Apr 8, 2021 · In unweighted graphs, it is a generalization of the Hamiltonian path problem, as a Hamiltonian path, if one exists, will be a longest path.
[15]
13.2 Hamilton paths and cycles
A Hamilton path is a path that visits every vertex of the graph.. The definitions of path and cycle ensure that vertices are not repeated. Hamilton paths ...<|separator|>
[16]
Path Graph -- from Wolfram MathWorld
The path graph P_n is a tree with two nodes of vertex degree 1, and the other n-2 nodes of vertex degree 2. A path graph is therefore a graph that can be ...
[17]
[PDF] An introduction to graph theory
... path graph Pn to be the simple graph. ({1, 2, . . . , n} , {{i, i + 1} | 1 ... Hamiltonian path in G means a walk of G that contains each vertex of G ...
[18]
[PDF] Introduction to Graph Theory
The graph obtained from Cn by removing an edge is the path graph on n vertices, denoted by Pn. ... Standard texts in graph theory include: 6. C. Berge, Graphs, ...
[19]
Petersen Graph -- from Wolfram MathWorld
Therefore, the Petersen graph is nonhamiltonian. In fact, it is also the smallest hypohamiltonian graph. The Petersen graph is one of two cubic graphs on 10 ...
[20]
[PDF] The Petersen Graph is not Hamiltonian - math.binghamton.edu
The Petersen graph is not Hamiltonian. If it were, a cycle would jump from the outer to inner cycle, and the next vertex would be either c0 or d0.
[21]
[PDF] 2 Trees
Proposition 2.3 Let T be a tree with |V (T)| ≥ 2. Then T has ≥ 2 leaf vertices. Further, if T has exactly 2 leaf vertices, then T is a path.
[22]
[PDF] A Linear Time Algorithm for the Minimum Spanning Caterpillar ...
Definition. By a caterpillar we mean a tree that reduces to a path by deleting all its leaves. We refer to the remaining path as the spine of the caterpillar.<|separator|>
[23]
[PDF] Math 355 Homework 8 Key 4.5 #4 - Oregon State University
Since any bipartite graph Km,n with m = n has a Hamiltonian cycle, we know that these graphs also have a Hamiltonian path. Additionally, without the restriction ...
[24]
[PDF] MATH 222 June 10, 2002 Redei's Theorem and the Camion-Moon
Jun 10, 2002 · Redei's Theorem states every tournament has a directed Hamiltonian path. Camion-Moon Theorem states every strongly connected tournament has a ...
[25]
(PDF) Hamilton Paths in Grid Graphs - ResearchGate
Aug 5, 2025 · The Hamilton path (and circuit) problem for general grid graphs is shown to be NP-complete. This provides a new, relatively simple, proof of the result.
[26]
Hamiltonian Paths in Some Classes of Grid Graphs
Apr 26, 2012 · Hamiltonian path in a graph is a simple path that visits every vertex exactly once. The problem of deciding whether a given graph has a ...
[27]
Hypotraceable Graph -- from Wolfram MathWorld
A graph G is a hypotraceable graph if G has no Hamiltonian path (i.e., it is not a traceable graph), but G-v has a Hamiltonian path (i.e., is a traceable ...Missing: definition | Show results with:definition
[28]
Hypohamiltonian/Hypotraceable Graphs and Facets - PubsOnLine
A graph G is called hypohamiltonian (hypotraceable) if it does not contain a hamiltonian cycle (chain) but if every vertex-deleted subgraph G − v contains a ...
[29]
5.3 Hamilton Cycles and Paths
There are some useful conditions that imply the existence of a Hamilton cycle or path, which typically say in some form that there are many edges in the graph.Missing: applications | Show results with:applications
[30]
[PDF] Hamilton Cycles
The problem of finding a Hamilton cycle in a graph has the same kind of origin as its Euler tour counterpart and the four colour problem: all three problems.<|separator|>
[31]
Some Theorems on Abstract Graphs - Dirac - 1952
This paper, 'Some Theorems on Abstract Graphs', by G.A. Dirac, was published in 1952 in the Proceedings of the London Mathematical Society.
[32]
[PDF] arXiv:2002.10014v5 [math.CO] 25 Jan 2021
Jan 25, 2021 · ... Dirac's theorem has a bipartite analogue, but Bondy's strengthened version of. Dirac's theorem also has a close analogue for bipartite graphs.
[33]
A theorem on paths in planar graphs - Wiley Online Library
We prove a theorem on paths with prescribed ends in a planar graph which extends Tutte's theorem on cycles in planar graphs.
[34]
[PDF] A Theorem on Graphs - Hassler Whitney
378. Page 3. I. A THEOREM ON GRAPHS. 379 n vertices, ice can construct a graph homeomorphic with it as follows: Draw a regular polygon of n ...
[35]
A THEOREM ON PLANAR GRAPHS
The generalized theorem (Theorem. I below) asserts that any planar graph having a circuit has one satisfying cer- tain specified conditions. For an important.Missing: cycle | Show results with:cycle
[36]
[2508.03531] Barnette Graphs with Faces up to Size 8 are Hamiltonian
Aug 5, 2025 · Barnette's conjecture states that every cubic, bipartite, planar and 3-connected graph is Hamiltonian. Goodey verified Barnette's conjecture for ...
[37]
The Planar Hamiltonian Circuit Problem is NP-Complete - SIAM.org
We consider the problem of determining whether a planar, cubic, triply-connected graph G has a Hamiltonian circuit. We show that this problem is NP-complete ...
[38]
[PDF] The Complexity of Theorem-Proving Procedures - Computer Science
S. A. Cook: such an improvement in 3A would require a major breakthrough in complexity theory. The field of mechanical theorem proving badly needs a basis ...Missing: Hamiltonian path<|separator|>
[39]
[PDF] CMSC 451: SAT, Coloring, Hamiltonian Cycle, TSP
Hence, Hamiltonian Path is NP-complete. Given n cities, and distances d(i,j) between each pair of cities, does there exist a path of length ≤ k that visits ...
[40]
A quantum approximate optimization algorithm for solving Hamilton ...
Apr 17, 2022 · Quantum approximate optimization algorithm (QAOA) is an effective algorithm that can obtain the optimal solution with high probability.
[41]
Hamiltonian path problem: the performance comparison ...
It is shown that it becomes inefficient to use branch-and-bound method, the most popular method which is realized on a computer, from the counted number of ...
[42]
[PDF] A non-standard branch and bound method for the Hamiltonian cycle ...
Nov 27, 2000 · In this section, we propose a Branch & Bound algorithm based on the above. Markov decision process embedding. We first introduce the notation ...
[43]
On the nearest neighbor rule for the metric traveling salesman problem
Nov 20, 2015 · Our construction proves for the first time a lower bound on the approximation ratio of the nearest neighbor rule for rectilinear TSP instances.
[44]
Application of an improved genetic algorithm to Hamiltonian circuit ...
A new constraint satisfaction optimization problem model for the circuit Hamiltonian circuit problem in a superimposed graph has been presented.
[45]
Optimal Hamiltonian completions and path covers for trees, and a ...
In this paper we first give a description and proof of correctness for this linear-time algorithm that is simpler and more intuitive than those given previously ...<|separator|>
[46]
[PDF] fast parallel algorithms for finding hamiltonian - UC Berkeley EECS
Theorem 1: Every tournament contains a Hamiltonian path. Proof: By induction on the number, n, of vertices. The result is clear for n=2. Assume it ...
[47]
The Hamiltonian Cycle and Travelling Salesperson problems with ...
The HCP was decided for the whole dataset using the Concorde TSP solver and the result of the experiment is shown in Fig. 5(a) - HCP (exact). The dataset ...
[48]
hamiltonian_path — NetworkX 3.5 documentation
Returns a Hamiltonian path in the given tournament graph. Each tournament has a Hamiltonian path. If furthermore, the tournament is strongly connected,
[49]
Exact methods for the longest induced cycle problem - ResearchGate
Aug 6, 2025 · We propose novel integer linear programming (ILP) formulations for the problem and discuss efficient implementations thereof. Comparing them ...
[50]
About the number of directed paths in tournaments - ScienceDirect
Apr 30, 2020 · Every tournament contains a directed Hamiltonian path. ... But according to Lemma 9, strong tournaments with 9 Hamiltonian paths have at most 5 ...
[51]
[PDF] approximation algorithms for path tsp
A generalization to the Metric TSP problem, called Metric Path TSP (or often just Path. TSP), asks for the shortest path between two fixed vertices which visits ...
[52]
Almost all optimally coloured complete graphs contain a rainbow ...
Jul 1, 2020 · We show that almost all optimal edge-colourings of K_{n} admit both (i) a rainbow Hamilton path and (ii) a rainbow cycle using all of the colours.Missing: colored | Show results with:colored
[53]
[PDF] Rainbow Hamilton cycles in random graphs - CMU Math
In this paper we consider the existence of rainbow Hamilton cycles in edge-colored graphs. ... The colored directed graph Γ contains a rainbow directed Hamilton ...
[54]
P vs NP - Clay Mathematics Institute
The P vs NP question asks if it's easy to check a solution if it's also easy to solve. P problems are easy to find, NP problems are easy to check.
[55]
[PDF] Hamilton Cycles in Random Graphs: a bibliography
Jul 4, 2021 · have minimum degree k then we should have a lower threshold. ... Shelah, Expected computation time for Hamiltonian path problem,. SIAM ...
[56]
[PDF] Hamiltonian Cycle and Hamiltonian Path and its Applications-A ...
These concepts find valuable applications in transportation, computer networks, circuit design, bioinformatics, robotics, game theory, DNA sequencing, urban ...
[57]
Euler and Hamiltonian Paths - GeeksforGeeks
Feb 3, 2025 · Applications in Engineering · Network Design: Hamiltonian cycles optimize routing and minimize network costs (e.g., fiber optic networks).