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.

We call  a Moore graph of degree and girth g, or, if , a Moore graph of degree  and diameter d.

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 we can suppose that G does not contain . So by the Theorem 10.4. there exist two non-adjacent vertices x and y, for which .

So, at least one of them, say x

.

Since  is not an extremal graph

which completes the proof.