Let $k\geq 2$. Prove that if $G$ is $k$-regular, then $G$ contains a cycle with at least $k+1$ edges.
The way I did it was to prove that the longest path in $G$ must have at least $k$ edges, and that such a path must be one short of a cycle, and thus the longest cycle must contain at least $k+1$ edges. Is this way correct? Are there other more direct ways of approaching this problem? Thanks!
Best Answer
sorry I see this is an old question, so my answer is probably overdue... I think the answer you are proposing is in essence correct, you must just make sure you also cover the case where the longest path contains more than $k$ edges. The key is to observe that for a longest path $P=v_1v_2\ldots v_l$, the vertex $v_l$ must be adjacent to $k$ vertices all contained in $P$, since $G$ is $k-$regular and $P$ is a longest path. So then if the path is longer than $k$ edges, pick the subpath containing only $v_l$ and the vertices adjacent to it (contains at least $k+1$ vertices). Now this subpath has as end-vertices $v_l$ and a vertex which is adjacent to $v_l$ (else this vertex would not be part of the subpath). Connecting this vertex with $v_l$ completes a cycle with at least $k+1$ edges.