7.2. Paths and Cycles
For a given graph G
denotes the
minimal degree of vertices and g is the girth and denotes the length of
a shortest cycle.
Theorem 7.1. For and
put
Then a graph G
with minimum degree and girth g
has at least
vertices.
Proof.
We will examine separately the two cases if g is even or odd.
-
Suppose
that
.
Let and
. We state that there is no two
paths of length
at most d.
Suppose the opposite.
Then the length of both paths .
So, and so we have
a cycle in G with length at most
, which contradicts that
.
In a connected graph G
the distance between two
vertices u and v is the minimum of the lengths of the
paths of G.
We can classify the vertices into different subsets according to their distance from the vertex x:
-
Since
, so there are at least
vertices at distance 1 from x.
-
We
can reach the vertices are distance 2
from x through vertices which are at distance 1 from x. So we have at least
vertices at distance 2.
-
The
number of vertices at distance 3
is at least
.
-
The
number of vertices at distance d is at least
.
So
-
Suppose
that
.
Pick two adjacent vertices, say x and y.
Then there are at least vertices at
distance 1 from
,
and at least vertices at
distance 2, and so on, ...,
at least vertices at
distance
from
.
So
Let us looking for an
extremal graph with parameters
and g.
The above theorem shows
that is regular of
degree
.
Furthermore,
- if
then
has diameter d and
- if
then every vertex is within distance
of each pair of
adjacent vertices.




Let us see now what we can say about long cycles and paths in a graph.
The length of a longest
cycle in a graph G is called as circumference. Example: the
circumference of a Hamiltonian graph is n, while the longest path is .
Is there any connection between the length of a circumference and the length of a longest path?
Theorem 7.2. Every non-Hamiltonian connected graph contains at least as long paths as the circumference of the graph.
Proof.
Let be a longest
cycle.
since
the graph is not Hamiltonian. Since
then there
exists a vertex
which is not on
C and is adjacent with a vertex of C, say
, and then
is a path of
length l.
Theorem 7.3. Let G be a connected graph
of order such that for
any two non-adjacent vertices x and y we have
.
-
If
then G is Hamiltonian.
-
If
then G contains a path of length k, and a cycle of length at least
.
Proof.
Suppose that G is
not Hamiltonian. Let be a longest
path in G.
Since P is
maximal, so all the neigbours of and
are in P.
As G does not
contain a cycle of length l, is not
adjacent to
.
The path P cannot
contain vertices and
such that
is adjacent to
and
is adjacent to
.
Since, otherwise is a
cycle of length l.
We define the following two sets:
These two sets are
disjoint subsets of and so
.
The first two assertions of the theorem follow from this inequality:
-
if
this is impossible, so G is Hamiltonian,
-
if
then P has length
.
It remains to prove the statement about cycles.
Assume that so
, where
denotes the
least integer not less than z.
Put . Then
and so G contains a cycle of length .
The Theorem 7.3. has the following consequence:
Theorem 7.4. Let G be a
graph of order n without a path of length . Then
.
A graph is an extremal graph (that is equality holds for it) iff all its components are complete graphs of order k.
Proof.
We fix k and apply induction on n.
- If
then the statement is trivial.
- Let
and suppose that the statetemnt is true for all
.
o If G is disconnected, the induction hypothesis implies the result.
o So we can suppose that G is connected.
If G contains (a complete k
order graph) then it has a path of length k.


So, at least one of them, say x
.
Since is not an
extremal graph
which completes the proof.