{{short description|Path in a graph that visits each vertex exactly once}} {{about|the nature of Hamiltonian paths|the question of the existence of a Hamiltonian path or cycle in a given graph|Hamiltonian path problem}} [[File:Hamiltonian Cycle.svg|thumb|A Hamiltonian cycle around a network of six vertices]] [[File:Натурализация гамильтоновых циклов.jpg|thumb|Examples of Hamiltonian cycles on a square grid graph 8x8]] In the [[mathematics|mathematical]] field of [[graph theory]], a '''Hamiltonian path''' (or '''traceable path''') is a [[path (graph theory)|path]] in an undirected or directed graph that visits each [[vertex (graph theory)|vertex]] exactly once. A '''Hamiltonian cycle''' (or '''Hamiltonian circuit''') is a [[cycle (graph theory)|cycle]] that visits each vertex exactly once. A Hamiltonian path that starts and ends at adjacent vertices can be completed by adding one more edge to form a Hamiltonian cycle, and removing any edge from a Hamiltonian cycle produces a Hamiltonian path. The computational problems of determining whether such paths and cycles exist in graphs are [[NP-complete]]; see [[Hamiltonian path problem]] for details.
Hamiltonian paths and cycles are named after [[William Rowan Hamilton]], who invented the [[icosian game]], now also known as ''Hamilton's puzzle'', which involves finding a Hamiltonian cycle in the edge graph of the [[dodecahedron]]. Hamilton solved this problem using the [[icosian calculus]], an [[algebraic structure]] based on [[root of unity|roots of unity]] with many similarities to the [[quaternion]]s (also invented by Hamilton). This solution does not generalize to arbitrary graphs.
Despite being named after Hamilton, Hamiltonian cycles in polyhedra had also been studied a year earlier by [[Thomas Kirkman]], who, in particular, gave an example of a polyhedron without Hamiltonian cycles.<ref>{{citation | last = Biggs | first = N. L. |author-link=Norman L. Biggs | doi = 10.1112/blms/13.2.97 | issue = 2 | journal = The Bulletin of the London Mathematical Society | mr = 608093 | pages = 97–120 | title = T. P. Kirkman, mathematician | volume = 13 | year = 1981}}.</ref> Even earlier, Hamiltonian cycles and paths in the [[knight's graph]] of the [[chessboard]], the [[knight's tour]], had been studied in the 9th century in [[Indian mathematics]] by [[Rudrata]], and around the same time in [[Mathematics in medieval Islam|Islamic mathematics]] by [[al-Adli ar-Rumi]]. In 18th century Europe, knight's tours were published by [[Abraham de Moivre]] and [[Leonhard Euler]].<ref>{{citation|title=Across the Board: The Mathematics of Chessboard Problems | first=John J.|last=Watkins|publisher=Princeton University Press|year=2004|pages=25–38|chapter=Chapter 2: Knight's Tours | isbn=978-0-691-15498-5}}.</ref>
==Definitions== A ''Hamiltonian path'' or ''traceable path'' is a [[path (graph theory)|path]] that visits each vertex of the graph exactly once. A graph that contains a Hamiltonian path is called a '''traceable graph'''. A graph is '''Hamiltonian-connected''' if for every pair of vertices there is a Hamiltonian path between the two vertices.
A ''Hamiltonian cycle'', ''Hamiltonian circuit'', ''vertex tour'' or ''graph cycle'' is a [[cycle (graph theory)|cycle]] that visits each vertex exactly once. A graph that contains a Hamiltonian cycle is called a '''Hamiltonian graph'''.
Similar notions may be defined for ''[[directed graph]]s'', where each edge (arc) of a path or cycle can only be traced in a single direction (i.e., the vertices are connected with arrows and the edges traced "tail-to-head").
A [[Hamiltonian decomposition]] is an edge decomposition of a graph into Hamiltonian circuits.
A ''Hamilton maze'' is a type of logic puzzle in which the goal is to find the unique Hamiltonian cycle in a given graph.<ref>{{cite book |last=de Ruiter |first=Johan |date=2017 |title=Hamilton Mazes – The Beginner's Guide}}</ref><ref>{{cite web| url=https://erich-friedman.github.io/puzzle/ham/ |title=Hamiltonian Mazes |last=Friedman |first=Erich |website=Erich's Puzzle Palace |access-date=23 October 2025 |url-status=live |archive-url=https://web.archive.org/web/20160416235225/http://www2.stetson.edu/~efriedma/puzzle/ham/ |archive-date=16 April 2016 }}</ref>
==Examples== {{Hamiltonian platonic graphs.svg}} * A [[complete graph]] with more than two vertices is Hamiltonian * Every [[cycle graph]] is Hamiltonian * Every [[tournament (graph theory)|tournament]] has an odd number of Hamiltonian paths ([[László Rédei|Rédei]] 1934) * Every [[platonic solid]], considered as a graph, is Hamiltonian<ref>[http://www.scientificamerican.com/magazine/sa/1957/05-01/ Gardner, M. "Mathematical Games: About the Remarkable Similarity between the Icosian Game and the Towers of Hanoi." Sci. Amer. 196, 150–156, May 1957] </ref> * The [[Cayley graph]] of a finite [[Coxeter group]] is Hamiltonian (see [[Lovász conjecture]] for a more general claim) * [[Cayley graph]]s on [[nilpotent group]]s with cyclic [[commutator subgroup]] are Hamiltonian.<ref>{{Cite journal| last1=Ghaderpour|first1=E.|last2=Morris|first2=D. W.|date=2014|title=Cayley graphs on nilpotent groups with cyclic commutator subgroup are Hamiltonian|journal=Ars Mathematica Contemporanea|language=en|volume=7|issue=1|pages=55–72| doi=10.26493/1855-3974.280.8d3| arxiv=1111.6216|s2cid=57575227 }}</ref> * The [[flip graph]] of a convex polygon or equivalently, the [[Tree rotation|rotation graph]] of [[binary tree]]s, is Hamiltonian.<ref>{{citation | last = Lucas | first = Joan M. | doi = 10.1016/0196-6774(87)90048-4 | issue = 4 | journal = Journal of Algorithms | pages = 503–535 | title = The rotation graph of binary trees is Hamiltonian | volume = 8 | year = 1987}}</ref><ref>{{citation | last1 = Hurtado | first1 = Ferran | author-link = Ferran Hurtado | last2 = Noy | first2= Marc | doi = 10.1016/S0925-7721(99)00016-4 | doi-access=free | issue = 3 | journal = [[Computational Geometry (journal)|Computational Geometry]] | pages = 179–188 | title = Graph of triangulations of a convex polygon and tree of triangulations | volume = 13 | year = 1999}}</ref>
==Properties== [[Image:Herschel Hamiltonian path.svg|thumb|The [[Herschel graph]] is the smallest possible [[polyhedral graph]] that does not have a Hamiltonian cycle. A possible Hamiltonian path is shown.]] Any Hamiltonian cycle can be converted to a Hamiltonian path by removing one of its edges, but a Hamiltonian path can be extended to a Hamiltonian cycle only if its endpoints are adjacent.
All Hamiltonian graphs are [[Biconnected graph|biconnected]], but a biconnected graph need not be Hamiltonian (see, for example, the [[Petersen graph]]).<ref>{{cite web|url=http://mathworld.wolfram.com/BiconnectedGraph.html|title=Biconnected Graph|author=[[Eric W. Weisstein]]|publisher=Wolfram MathWorld}}</ref>
An [[Eulerian graph]] {{mvar|G}} (a [[connected graph]] in which every vertex has even degree) necessarily has an Euler tour, a closed walk passing through each edge of {{mvar|G}} exactly once. This tour corresponds to a Hamiltonian cycle in the [[line graph]] {{math|''L''(''G'')}}, so the line graph of every Eulerian graph is Hamiltonian. Line graphs may have other Hamiltonian cycles that do not correspond to Euler tours, and in particular the line graph {{math|''L''(''G'')}} of every Hamiltonian graph {{mvar|G}} is itself Hamiltonian, regardless of whether the graph {{mvar|G}} is Eulerian.<ref>{{citation|title=A Textbook of Graph Theory| first1=R.|last1=Balakrishnan| first2=K.|last2=Ranganathan| publisher=Springer| year=2012| isbn=9781461445296| contribution=Corollary 6.5.5|page=134|url=https://books.google.com/books?id=mpgu6wgnZgYC&pg=PA134}}.</ref>
A [[Tournament (graph theory)|tournament]] (with more than two vertices) is Hamiltonian if and only if it is [[Strongly connected component|strongly connected]].
The number of different Hamiltonian cycles in a complete undirected graph on {{mvar|n}} vertices is {{math|{{sfrac|(''n'' − 1)!|2}}}} and in a complete directed graph on {{mvar|n}} vertices is {{math|(''n'' − 1)!}}. These counts assume that cycles that are the same apart from their starting point are not counted separately.
== Bondy–Chvátal theorem ==
The best vertex [[degree (graph theory)|degree]] characterization of Hamiltonian graphs was provided in 1972 by the [[J. A. Bondy|Bondy]]–[[Václav Chvátal|Chvátal]] theorem, which generalizes earlier results by [[Gabriel Andrew Dirac|G. A. Dirac]] (1952) and [[Øystein Ore]]. Both Dirac's and Ore's theorems can also be derived from [[Pósa theorem|Pósa's theorem]] (1962). Hamiltonicity has been widely studied with relation to various parameters such as graph [[Dense graph|density]], [[Graph toughness|toughness]], [[Forbidden subgraph problem|forbidden subgraphs]] and [[Distance (graph theory)|distance]] among other parameters.<ref>{{Cite web|url = http://www.mathcs.emory.edu/~rg/advances.pdf|title = Advances on the Hamiltonian Problem – A Survey|date = July 8, 2002|access-date = 2012-12-10|publisher = Emory University|last = Gould|first = Ronald J.|archive-date = 2018-07-13|archive-url = https://web.archive.org/web/20180713030433/http://www.mathcs.emory.edu/~rg/advances.pdf|url-status = dead}}</ref> Dirac and Ore's theorems basically state that a graph is Hamiltonian if it has ''enough edges''.
The Bondy–Chvátal theorem operates on the '''closure''' {{math|cl(''G'')}} of a graph {{math|''G''}} with {{mvar|n}} vertices, obtained by repeatedly adding a new edge {{math|''uv''}} connecting a [[nonadjacent]] pair of vertices {{math|''u''}} and {{math|''v''}} with {{math|deg(''v'') + deg(''u'') ≥ ''n''}} until no more pairs with this property can be found.
{{math theorem | name = Bondy–Chvátal Theorem (1976) | math_statement = A graph is Hamiltonian if and only if its closure is Hamiltonian.}}
As complete graphs are Hamiltonian, all graphs whose closure is complete are Hamiltonian, which is the content of the following earlier theorems by Dirac and Ore.
{{math theorem | name = Dirac's Theorem (1952) | math_statement = A [[simple graph]] with {{mvar|n}} vertices (<math>n\geq 3</math>) is Hamiltonian if every vertex has degree <math>\tfrac{n}{2}</math> or greater.}}
{{math theorem | name = [[Ore's theorem|Ore's Theorem]] (1960) | math_statement = A [[simple graph]] with {{mvar|n}} vertices (<math>n\geq 3</math>) is Hamiltonian if, for every pair of non-adjacent vertices, the sum of their degrees is {{mvar|n}} or greater.}}
The following theorems can be regarded as directed versions:
{{math theorem | name = Ghouila–Houiri (1960) | math_statement = A [[strongly connected graph|strongly connected]] [[simple graph|simple]] [[directed graph]] with {{mvar|n}} vertices is Hamiltonian if every vertex has a full degree greater than or equal to {{mvar|n}}.}}
{{math theorem | name = Meyniel (1973) | math_statement = A [[strongly connected graph|strongly connected]] [[simple graph|simple]] [[directed graph]] with {{mvar|n}} vertices is Hamiltonian if the sum of full degrees of every pair of distinct non-adjacent vertices is greater than or equal to <math>2n-1</math>}}
The number of vertices must be doubled because each undirected edge corresponds to two directed arcs and thus the degree of a vertex in the directed graph is twice the degree in the undirected graph.
{{math theorem | name = Rahman–[[Mohammad Kaykobad|Kaykobad]] (2005) | math_statement = A [[simple graph]] with {{mvar|n}} vertices has a Hamiltonian path if, for every non-adjacent vertex pairs the sum of their degrees and their shortest path length is greater than {{mvar|n}}.<ref>{{Cite journal|title = On Hamiltonian cycles and Hamiltonian paths|last1 = Rahman|first1 = M. S.|date = April 2005|journal = Information Processing Letters|doi = 10.1016/j.ipl.2004.12.002|last2 = Kaykobad|first2 = M.|volume = 94|pages = 37–41}}</ref>}}
The above theorem can only recognize the existence of a Hamiltonian path in a graph and not a Hamiltonian Cycle.
Many of these results have analogues for balanced [[bipartite graph]]s, in which the vertex degrees are compared to the number of vertices on a single side of the bipartition rather than the number of vertices in the whole graph.<ref>{{citation | last1 = Moon | first1 = J. | last2 = Moser | first2 = L. | author2-link = Leo Moser | doi = 10.1007/BF02759704 | journal = [[Israel Journal of Mathematics]] | mr = 0161332 | pages = 163–165 | title = On Hamiltonian bipartite graphs | volume = 1 | issue = 3 | year = 1963| s2cid = 119358798 }}</ref>
== Existence of Hamiltonian cycles in planar graphs == {{math theorem | math_statement = A 4-connected planar triangulation has a Hamiltonian cycle.<ref>{{citation | last = Whitney | first = Hassler | author-link = Hassler Whitney | doi = 10.2307/1968197 | issue = 2 | journal = Annals of Mathematics | mr = 1503003 | pages = 378–390 | series = Second Series | title = A theorem on graphs | volume = 32 | year = 1931| jstor = 1968197}}</ref>}}
{{math theorem | math_statement = A 4-connected planar graph has a Hamiltonian cycle.<ref>{{citation | last = Tutte | first = W. T. | author-link = W. T. Tutte | doi = 10.1090/s0002-9947-1956-0081471-8 | journal = Trans. Amer. Math. Soc. | pages = 99–116 | title = A theorem on planar graphs | volume = 82 | year = 1956| doi-access = free}}</ref>}}
== The Hamiltonian cycle polynomial ==
An algebraic representation of the Hamiltonian cycles of a given weighted digraph (whose arcs are assigned weights from a certain ground field) is the [[Hamiltonian cycle polynomial]] of its weighted adjacency matrix defined as the sum of the products of the arc weights of the digraph's Hamiltonian cycles. This polynomial is not identically zero as a function in the arc weights if and only if the digraph is Hamiltonian. The relationship between the computational complexities of computing it and [[computing the permanent]] was shown by Grigoriy Kogan.<ref>{{Cite book| first = Grigoriy |last = Kogan |title = Proceedings of 37th Conference on Foundations of Computer Science |chapter = Computing permanents over fields of characteristic 3: Where and why it becomes difficult |pages = 108–114 | year = 1996 |doi = 10.1109/SFCS.1996.548469 |isbn = 0-8186-7594-2 |s2cid = 39024286 }}</ref>
==See also== {{div col|colwidth=30em}} * [[Barnette's conjecture]], an open problem on Hamiltonicity of cubic [[bipartite graph|bipartite]] [[polyhedral graph]]s * [[Eulerian path]], a path through all edges in a graph * [[Fleischner's theorem]], on Hamiltonian [[power of graph|squares of graphs]] * [[Gray code]] * [[Grinberg's theorem]] giving a necessary condition for [[planar graph]]s to have a Hamiltonian cycle * [[Hamiltonian path problem]], the computational problem of finding Hamiltonian paths * [[Hypohamiltonian graph]], a non-Hamiltonian graph in which every vertex-deleted subgraph is Hamiltonian * [[Knight's tour]], a Hamiltonian cycle in the [[knight's graph]] * [[LCF notation]] for Hamiltonian [[cubic graph]]s. * [[Lovász conjecture]] that [[vertex-transitive graph]]s are Hamiltonian * [[Pancyclic graph]], graphs with cycles of all lengths including a Hamiltonian cycle *[[Panconnectivity]], a strengthening of both pancyclicity and Hamiltonian-connectedness * [[Seven Bridges of Königsberg]] * [[Shortness exponent]], a numerical measure of how far from Hamiltonian the graphs in a family can be * [[Snake-in-the-box]], the longest [[induced path]] in a hypercube * [[Steinhaus–Johnson–Trotter algorithm]] for finding a Hamiltonian path in a [[permutohedron]] * [[Subhamiltonian graph]], a subgraph of a [[planar graph|planar]] Hamiltonian graph * [[Tait's conjecture]] (now known false) that 3-regular [[polyhedral graph]]s are Hamiltonian * [[Travelling salesman problem]] * [[Harris graph|Harris graphs]], a family of graphs that are tough, [[Eulerian path|Eulerian]], and non-Hamiltonian{{div col end}}
==Notes== {{reflist}}
== References == * {{citation | last1 = Berge | first1 = Claude | author1-link = Claude Berge | last2 = Ghouila-Houiri | first2 = A. | location = New York | publisher = Sons, Inc. | title = Programming, games and transportation networks | year = 1962}} *{{citation | last = DeLeon | first = Melissa | issue = 1 | journal = Rose-Hulman Undergraduate Math Journal | title = A study of sufficient conditions for Hamiltonian cycles | url = http://www.rose-hulman.edu/mathjournal/archives/2000/vol1-n1/paper4/v1n1-4pd.PDF | volume = 1 | year = 2000 | access-date = 2005-11-28 | archive-url = https://web.archive.org/web/20121222070642/http://www.rose-hulman.edu/mathjournal/archives/2000/vol1-n1/paper4/v1n1-4pd.PDF | archive-date = 2012-12-22 | url-status = dead }}. *{{citation | last = Dirac | first = G. A. | author-link = Gabriel Andrew Dirac | doi = 10.1112/plms/s3-2.1.69 | mr = 0047308 | journal = Proceedings of the London Mathematical Society | series = 3rd Ser. | pages = 69–81 | title = Some theorems on abstract graphs | volume = 2 | year = 1952}}. *{{citation | last = Hamilton | first = William Rowan | author-link = William Rowan Hamilton | journal = [[Philosophical Magazine]] | page = 446 | title = Memorandum respecting a new system of roots of unity | volume = 12 | year = 1856}}. *{{citation | last = Hamilton | first = William Rowan | author-link = William Rowan Hamilton | journal = [[Proceedings of the Royal Irish Academy]] | pages = 415–416 | title = Account of the Icosian Calculus | volume = 6 | year = 1858}}. *{{citation | last = Meyniel | first = M. | doi = 10.1016/0095-8956(73)90057-9 | issue = 2 | journal = [[Journal of Combinatorial Theory]] | mr = 0317997 | pages = 137–147 | series = Series B | title = Une condition suffisante d'existence d'un circuit hamiltonien dans un graphe orienté | volume = 14 | year = 1973| doi-access = free }}. *{{citation | last = Ore | first = Øystein | author-link = Øystein Ore | journal = The American Mathematical Monthly | jstor = 2308928 | mr = 0118683 | doi = 10.2307/2308928 | page = 55 | title = Note on Hamilton circuits | volume = 67 | issue = 1 | year = 1960}}. *{{citation | last = Pósa | first = L. | author-link = Lajos Pósa (mathematician) | journal = Magyar Tud. Akad. Mat. Kutató Int. Közl. | mr = 0184876 | pages = 225–226 | title = A theorem concerning Hamilton lines | volume = 7 | year = 1962}}.
==External links== * {{MathWorld|title=Hamiltonian Cycle|urlname=HamiltonianCycle}} * [https://web.archive.org/web/20120309190309/http://www.graph-theory.net/euler-tour-and-hamilton-cycles/ Euler tour and Hamilton cycles]
[[Category:Computational problems in graph theory]] [[Category:NP-complete problems]] [[Category:Graph theory objects]] [[Category:Hamiltonian paths and cycles| ]] [[Category:William Rowan Hamilton]]