[Math] Show that $G$ contains a cycle of length at least $\sqrt k$.

Question

Let $G$ be a graph containing a cycle $C$, and assume that $G$ contains a path of length at least $k$ between two vertices of $C$. Show that G contains a cycle of length at least $\sqrt k$. Is this the best possible?

Answer 1

Let $v_1,\dots,v_t$ be the common points on the path and the cycle. If $t\geq \sqrt{k}$, then $C$ has at least $\sqrt{k}$ vertices then the proof is complete. In the other case, for some $i$, there is a part of the path between $v_i$ and $v_{i+1}$ that contains at least $\sqrt{k}$ edges. Now if you take the part of the path together with a path between $v_i$ and $v_{i+1}$ along the cycle, then you will get a cycle of length at least $\sqrt{k}$ as desired.