Some basic Theorems about Graphs in Exercises: Part 5.
--
This story belongs to a contiguous series with the aim to list some of the basic theorems of graph theory. It is intentionally written in form of exercises to invite the reader having a ‘learning experience by doing’. In this sense it is not important to have solved any of these exercises but it is important to have tried them for a couple of minutes.
As usually in this series, all graphs are assumed to be simple, undirected and finite, except otherwise mentioned.
Problem 1:
A graph that has a degree
k
wherek
is greater than1
has a cycle of length at leastk+1
.
Recall, a cycle is a path for that the starting and ending vertexes coincides. The degree of a vertex is the number of its neighbors and the degree of a graph is the minimal degree over all vertexes.
Solution:
We can construct such a cycle by the following technique. Start with any vertex v_1
. Since deg(v_1) > 1
there must be some adjacent vertex v_2
. The latter has k-1
adjacent vertexes that are different from v_1
. Since k-1 >/= 1
, there must be such a vertex v_3
. Now, v_3
again has k-2
adjacent vertexes distinct from v_1
and v_2
. Let us assume we had constructed a path (v_1, v_2, ..., v_k)
, then v_k
has at least 1
adjacent vertexes distinct from {v_1, ..., v_{k-1}}
. We denote this vertex by v_{k+1}
to obtain the path:
{v_1, v_2, ..., v_{k+1}}
Note, by construction this is no cycle so far. We follow-up with this construction and consider the k-1
neighbors of v_{k+1}
. If one of these is v_1
, we are done (cycle with length k+1
). Otherwise, we can find one of these neighbors, called v_{k+2}
, that is different from the k-1
vertexes {v_1, v_2, v_3, ..., v_{k-1}}
.
Again, if v_{k+2}
has a neighbor that coincides with v_1
or v_2
, we are done. Else we can proceed like in the previous step.
Sometimes this procedure must come to a step where v_{i+k}
has a neighbor that coincides with any…