Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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.

share|cite|improve this question
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

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.

share|cite|improve this 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$.

share|cite|improve this answer

Your Answer


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.