2.1. Hamiltonian Graphs
A vertex u is said to be
connected to a vertex v in a graph G if there exists a path in G.
A graph is connected if every two of its vertices are connected. Otherwise the graph is disconnected.
If G is connected
and is disconnected, where W is a set of
vertices, then we say that W separates G, or that W is a vertex-cut .
If in two vertices s and t belong to
different components then W separates s from t.
A graph G is k-vertex-connected
if
-
either
-
or it has at least
vertices and no set of
vertices separate G.


The vertex-connectivity
- - of a graph G is
-
the minimum cardinality of a vertex-cut if G is not complete, and
-
if
for some positive integer n.
Two nonadjacent vertices in a graph are said to be independent.
A set S of vertices is independent if every two vertices of S are independent.
The vertex independence
number of a graph G is the maximum cardinality
among the independent sets of vertices of G.
If G is a
noncomplete graph and t is a nonnegative real number such that for every vertex-cut S of G and
,
then G is defined t-tough. (Here
means the number of components of a graph G.)
If G is t-tough
and s is a nonnegative real number such that ,
then G is also s-tough.
The maximum real number t
for which a graph G is t-tough is called the toughness of G
and denoted by .
Since complete graphs do
not contain vertex-cuts, this definition does not apply to such graphs. We
define for every positive integer n.
The independence number
is related to the toughnes in the sense that among all the vertex-cuts S
of a noncomplete graph G, the maximum value of is
, so
for every vertex-cut S of G, we have that
.
Theorem 2.1. Let G be a k-connected
graph, . Then
every k vertices of G lie on a common cycle of G.
Theorem 2.2. If G is a k-connected graph and are
distinct vertices of G,
then there exist internally disjoint
paths
.