Let $G$ be a graph of minimum degree $k>1$. Show that $G$ has a cycle of length at least $k+1$

Solution 1:

Let $P=v_0v_1 \dots v_l$ be a longest path in $G$. $v_0$ has to have additional neighbors by the degree constraint. All of the neighbors of $v_0$ have to be in $P$, otherwise $P$ could be extended. Also, from the degree constraint $v_0$ has at least $k$ neighbors in $P$. Let $j$ be the maximum index of a neighbor of $v_0$. By the previous statement we have that $j \ge k$. Thus we have the cycle $v_0v_1 \dots v_jv_0$, which has length at least $k+1$.

Solution 2:

This can be solved via the well-ordering principle. Let path P be the longest path in graph G that starts at point A, which has the lowest degree of the graph. If A has degree higher than 2, then it will have some neighboring point W. If W was not on P, then A would have a neighbor that's not on P, and then P would not be the longest path, so unless A's other neighbor is on the path as well, this creates a contradiction. As a result, W has to be on P, otherwise we'd have the said contradiction, meaning that all of A's neighbors are on P. This creates a cycle, and since a cycle has length of at least |V(G)| + 1, this path will have length of at least k + 1.

If there is an error with this, I just learned this in class about a week ago, so I'm far from perfect.