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