5.1. Hamiltonia graphs

Theorem 5.1. If G is hamiltonian then G is 2-connected.

Proof. If G is hamiltonian, then G is connected and contains a hamiltonian cycle. So, G has no cut-vertices and G has order at least 3. Therefore G is 2-connected.

Theorem 5.2. If G is a hamiltonian graph, then for every and then

.

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?

Theorem 5.3. (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 non-hamiltonian graph G of order that satisfies the hypothesis of the theorem.

Then G is non-hamiltonian - 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 , then . For otherwise , is a hamiltonian cycle of G.

Hence for each vertex of adjacent to u1 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 5.4. (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 5.3. - we arrive at the contradiction .

So, G must be hamiltonian.

Is there any other - easier - way to decide whether a graph is hamiltonian or not?

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.

 

 

 

Figure 5.3. Turning out recursively a closure of a graph

It is easy to see that the closure is well-defined, i.e. it is unique.

Theorem 5.5. A graph is hamiltonian iff its closure is hamiltonian.

Proof. The statement is a simple consequence of the definition of closure and the Theorem 5.4.

Theorem 5.6. 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.

Following the ides of closure, we can introduce a new - but similar - definition:

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.

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.

Theorem 5.7. (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 consists of G together with a new vertex w and the edges  uw and vw. So, H has of order .

Since is complete , so

Thus . So

.

Therefore and by Theorem 5.6, H is hamiltonian.

Any hamiltonian cycle of H contains the edges uw and vw, so G has a hamiltonian path.

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

,

then G is hamiltonian-connected.

Corollary 5.9. If G is a graph of order n such that for every vertex v of G, then G is hamiltonian-connected.