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!

  • $\begingroup$ Your approach would work, though you mean "must contain at least $k+1$ edges". $\endgroup$
    – Calvin Lin
    Jul 1 '13 at 15:32

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.

  • 1
    $\begingroup$ Well it's always good to see unanswered questions answered! =) $\endgroup$
    – user21820
    Jul 14 '14 at 6:15

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.