2
$\begingroup$

Let $k \geq 2$, let $G$ be a graph. Prove that if every vertex at least $k$, then $G$ contains a cycle of length atleast $k+1$.

I thought about proving this with a contradiction but I can't find a proof that proves that there exists no such cycle with length atleast $k+1$. I know there's a proof stating that if every vertex has degree at least $2$ then there exists some cycle, is this related to that proof in any way?

$\endgroup$
2
$\begingroup$

I assume the necessary condition that $G$ has finitely many vertices. Select an arbitrary vertex, $v_1$, and select any adjacent vertex, $v_2$. Then from the vertices connected to $v_2$, select any vertex not equal to $v_1$ and call it $v_3$. Continue in this fashion, each time selecting a vertex connected to $v_{n}$ not in the set $\{v_1,\ldots, v_{n-1}\}$. You can do this guaranteed at least until $n=k$ as each vertex has degree at least $k$. After this point the path has length $k-1$ as desired, so select another vertex connected to $v_k$ not in $\{v_2,\ldots, v_k\}$ and continuing not allowing for $v_n$ anything from $\{v_{n-k+1},\ldots, v_{n-1}\}$, and continue until you complete a cycle. The length is at least $k$ by construction.

$\endgroup$

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.