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?

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.