I don't understand why this stands:
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$.
Then $G$ contains a cycle of length at least $\sqrt{k}$.
Since we can extend the cycle $C$ with the vertices of the path, why don't we get a cycle of length $k+2$? ($2$ being the minimum number of vertices belonging to $C$ between the vertices where $C$ connect to it).
I really don't see where that square root is coming from.
For reference this is exercise $3$ from Chapter $1$ of the Diestel book.
Best Answer
Here is my solution. Let $s$ and $t$ two vertices of $C$ such that there is a $st$-path $P$ of lenght $k$. If $|V(P) \cap V(C)|\geq \sqrt{k}$ then the proof follows, because the cycle we want is $C$. Otherwise, consider that $|V(P) \cap V(C)| < \sqrt{k}$. Then, as $|V(P)| \geq k$, by pigeon principle, there is a subpath of $P$ of size at least $\sqrt{k}$ internally disjoint from some subpath of $C$. Joining this subpaths we get the desired.