Some basic Theorems about Graphs in Exercises: Part 5.

Join Medium with my referral link - applied.math.coding

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 where k is greater than 1 has a cycle of length at least k+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…