# Maximum cycle in a graph with a path of length $k$

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.

-
G contains a path of length at least k between ANY 2 vertices. right ? –  Amr Jun 19 '13 at 2:13
@user14111 yes i do mean path, corrected, thanks –  MasterScrat Jun 19 '13 at 21:07

## 1 Answer

The complete graph on $k+1$ vertices shows why you can't get a cycle of length $k+2$. The following example shows why, if you're looking for a long cycle, the best you can hope for in general is a constant times the square root of $k$:

Let $V(G)=\{v_0,v_1,\dots,v_{4n^2}\}$, $E(G)=\{v_iv_{i+1}:0\le i<4n^2\}\cup\{v_{jn}v_{(j+2)n}:0\le j\le{4n-2}\}$. In $G$ there is a path of length $k=4n^2$, each pair of vertices lies on a cycle, and the longest cycle has length $6n-1=3\sqrt{k}-1$.

-