CMI2016-B-2b

Question

A $\textit{simple path}$ (respectively cycle) in a graph is a path (respectively cycle) in which no edge or vertex is repeated. The $length$ of such a path (respectively cycle) is the number of edges in the path (respectively cycle).
Let $G$ be an undirected graph with minimum degree $k \geq 2$. Show that $G$ contains a simple cycle of length at least $k+1$.

Comments

Proof by Induction:

Inductive Step:

If k=2, we will get complete graph K3. It has cycle length of 3(k=2+1).

If k=3,complete graph K4 is obtained and it has cycle length of 4(k=3+1).

If k=n-1,Complete graph of K(n-1) is obtained, cycle length is n (k=n-1+1)

Hypothesis Step:

If k=n, Kn is obtained and cycle length is n+1 from the inductive steps.

Answer 1