Editing Hamiltonian path (section)

== 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>