# 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` 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…