View source for Hamiltonian path

{{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.png|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.
 | 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=http://www2.stetson.edu/~efriedma/puzzle/ham/ |title=Hamiltonian Mazes |last=Friedman |first=Erich |date=2009 |website=Erich's Puzzle Palace |access-date=27 May 2017 |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  (For more information on Hamiltonian paths in Cayley graphs, see the [[Lovász conjecture]].)
* [[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 Weinstein|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]]