2.2 Hamilton cycles and Hamilton paths
The traveling salesman problem: a salesman is to make a tour of n cities, at the end of which he has to return to the head office he starts from. The cost of the journey between any two cities is known.
The problem asks for an efficient algorithm for finding a least expensive tour.
A cycle containing all the vertices of a graph is said to be a Hamiltonian cycle.
A graph containing a Hamilton cycle is said to be Hamiltonian.
The origin of this term is a game invented in 1857 by Sir William Rowan Hamilton based on the construction of cycles containing all vertices in the graph of the dodecahedron.
In 1855 Thomas P. Kirkman posed the following question: Given the graph of a polyhedron, can one always find a circuit that passes through each vertex once and only once?

In fact, Hamilton cycles and paths in special graphs had been studied well before Hamilton proposed his game.
The puzzle of the knight`s tour on a chessboard, throughly analysed by Euler in 1759, ask for a Hamilton cycle in the graph whose vertices are the 64 squares of a chessboard and in which two vertices are adjacent if a knight can jump from one square to the other.
Theorem 2.3. If G is hamiltonian then G is 2-connected.
Theorem 2.4. If G is a hamiltonian graph, then for
every
.
Proof.
Let S be a proper nonempty
subset of , and suppose that
, where
are the components of
. Let C be a hamiltonian cycle
of G.
When C leaves ,
,
then the next vertex of C belongs to S. Thus
.
What about the sufficient conditions?
The above necessarily conditions are not sufficient aswell. For example, every hamiltonian graph is 2-connected, but the converse is not true.
No connectivity guaranties that a graph is hamiltonian.
Theorem 2.5. (O.
Ore, 1960): If G is a
graph of order such that for all distinct nonadjacent
vertices u and v
then G is hamiltonian.
Proof.
Suppose that the theorem is not true, i.e. there
exists a maximal nonhamiltonian graph G of order that satisfies the hypothesis of the theorem.
Then G is nonhamiltonian - so, it is not
complete - and every two nonadjacent vertices and
of G, the graph
is hamiltonian.
Let u and v two nonadjacent vertices
of G. Thus, is hamiltonian and every hamiltonian cycle of
contains the edge uv.


If . For otherwise
is a hamiltonian cycle of G.
Hence for
each vertex of adjacent to
there exists at least one vertex
from
which is not adjacent with un.
So
and this implies that there is a nonadjacent vertex-pair in G for which
which is a contradiction.
Theorem 2.6. (J. A. Bondy, V. Chvatal, 1976): Let u and v be distinct nonadjacent vertices of a graph G of order n such that
.
Then is hamiltonian iff G is hamiltonian.
Proof.
If G is hamiltonian and u and v are nonadjacent
vertices, then is also hamiltonian.
Suppose that G is a graph of order n
with nonadjacent vertices u and v such that and
is hamiltonian.
If G is not hamiltonian then - similarly to the proof of the Theorem 2.4. - we arrive at the contradiction
.
So, G must be hamiltonian.
The closure - - of a graph G
of order n is the graph obtained from G by recursively joining
pairs of nonadjacent vertices whose degree sum is at least n
until no such pairs remains.
Is the closure of a graph well-defined?
Theorem 2.7. If and
are two graphs obtained from a graph G of order n by
recursively joining pairs of nonadjacent vertices whose degree sum is at least n,
then
.
Proof.
Let and
be the sequences of edges added to G
obtained
and
, respectively.
It is enough to show that each is an edge of
and that each
is an edge of
.




Let the graph obtained from G by adding the
edges
.


By the choice of ,
is a subgraph of
, and
therefore
.
This is a contradiction, since u and v
are nonadjacent vertices of , so while constructing
, we
must to choose it.



So,
.
Theorem 2.8. A graph is hamiltonian iff its closure is hamiltonian.
Proof.
The Theorem is a simple consequence of the definition of closure and the Theorem 2.6.
Theorem 2.9. Let G be a graph with at least
three vertices. If is complete,
then G is hamiltonian.
Proof.
The statement follows from the fact that each complete graph is hamiltonian.
If a graph G satisfies the condition
of Theorem 2.5, then is complete and so, by Theorem 2.7., G is hamiltonian.
Thus, Ore's theorem is an immediate corollary of Theorem 2.9. (although chronologically it preceeded the theorem of Bondy and Chvatal by several years).
Perhaps surprisingly, many well-known sufficient condition for a graph to be hamiltonian based on vertex degrees can be deduced from Theorem 2.9.
The next theorem. due to Chvatal, is an example of one of the strongest of these:
Theorem
2.10. (V. Chvatal, 1972): Let G be a graph of order , the degrees
of whose vertices satisfy
. If there is no
integer
for which
,
then G is hamiltonian.
Proof.
We will show that is complete which, by the Theorem 2.10, implies that G is hamiltonian. Assume, to the contrary, that
is not complete.
Let u and w be nonadjacent
vertices of for which
is as large as possible.










Similarly, let U denote the vertices other
then u that are not adjacent to u in .
Then .



However, , so
.
This, however, contradicts the hypothesis of the theorem.
Corollary 2.11. (Dirac, 1952): If G is a graph of
order such that
for every vertex of G, then G is
hamiltonian.
In the case of regular graphs this statement can be improved: Jackson showed (1980) that every 2-connected r-regular graph of order at most 3r is hamiltonian. (The Petersen graph shows that 3r cannot be replaced by 3r+1.)
Theorem 2.12. (P. Erdős, V. Chvatal, 1972): Let G be a
graph with at least three vertices. If then G is hamiltonian.
Proof.
If then the result follows since G is
complete.
Assume that . Let
.
Since , G contains at least
one cycle. Among all cycles of G, let C be a maximum length
cycle. By Theorem 2.1. there are at least k
vertices on C. We will show that
that C is hamiltonian.
We will show that that C is hamiltonian.
Suppose the contrary. Then there exists a vertex w of G that does not lie on C.
Since , we may apply the Theorem 2.2. to conclude that
that there are k paths
having initial
vertex w that are pairwise disjoint, except for w, and that share
with C only their terminal vertices
respectively.
If any two of the vertices vi are consecutive on C, then there is a cycle containing more vertices than C has.



No vertex is adjacent to w
in G.
Otherwise we could replace the edge in C
by the
path determined
by the path
and the edge
to obtain a
cycle having length at least
, which is impossible.










A path in a graph G containing every vertex of G is called a hamiltonian path.
A graph is hamiltonian-connected if for every pair u,v of
distinct vertices, there exists a hamiltonian path.
A hamiltonian-connected graph with at least three vertices is hamiltonian.
The -closure
of a graph G
of order n to be the graph obtained from G by recursively joining
pairs of nonadjacent vertices whose degree sum is at least
until no such
pair remains.
Theorem 2.13. (J. A. Bondy and V. Chvatal, 1976): Let G be a graph of
order n. If is complete,
then G is hamiltonian-connected.
Proof.
If then the result is obvious, so we can suppose
that
.




Since is complete , so
Thus for
. So
.
Therefore and so, H is hamiltonian.
Any
hamiltonian cycle of H contains the edges and
, so G has a
hamiltonian
path.
,
then G is hamiltonian-connected.
Corollary 2.15. If G is a graph of order n such
that for every vertex v of G, then G is hamiltonian-connected.