Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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!

share|improve this question
    
Your approach would work, though you mean "must contain at least $k+1$ edges". –  Calvin Lin Jul 1 '13 at 15:32

1 Answer 1

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.

share|improve this answer
    
Well it's always good to see unanswered questions answered! =) –  user21820 Jul 14 at 6:15

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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