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.

Then there is a  path  containing every vertex of G.

 

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 .

Assume, to the contrary, that this is not the case, i.e. for some , , and the edge  does not belong to .

 

Let  the graph obtained from G by adding the edges .

It follows from the definition of  that .

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.

Thus each ei belongs to , and - by the symmetricity - we can also prove that each  belongs to .

 

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.

Since u and w are nonadjacent it follows that .
W.l.o.g. we can suppose that .

 

If  then  and .
Let W denote the vertices other than w that are not adjacent to w in . Then .
Also, by the choice of u and w, every vertex  satisfies .
Thus, G has at least k vertices of degree at most k and so .

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

 

Then .

Every vertex  satisfies , implying that .

 

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.

For each , let  be the vertex following   in some fixed cyclic ordering of C.

 

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.

Let . Since  and  for , there are integers j and l such that .
Thus by deleting the edges  and  from C and adding the edge  together with the paths  and , we obtain a cycle of G that is longer than C.
This produces a contradiction, so that C is a hamiltonian cycle of G.

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 .

Let G be a graph of order n whose -closure is complete, and let u and v be any two vertices of G.

 

Let H be a graph which consist of G together with a new vertex w and the edges  and . So, H has of order .

 

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.

Corollary 2.14. If G is a graph of order n such that for all distinct nonadjacent vertices u and v,

,

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.