7
$\begingroup$

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.

$\endgroup$
2
  • 1
    $\begingroup$ G contains a path of length at least k between ANY 2 vertices. right ? $\endgroup$
    – Amr
    Jun 19, 2013 at 2:13
  • $\begingroup$ @user14111 yes i do mean path, corrected, thanks $\endgroup$ Jun 19, 2013 at 21:07

3 Answers 3

6
$\begingroup$

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.

$\endgroup$
2
$\begingroup$

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$.

$\endgroup$
1
$\begingroup$

Let $\{v_1,…,v_n\}$ be common vertices along the $xy$-path $P$ and the cycle $C$. Suppose $n≥\sqrt{k}$. As a result, $C$ has at least $\sqrt{k}$ vertices, so it is a cycle of length at least $\sqrt{k}$.

However, suppose $n<\sqrt{k}$. The cycle interrupts $P$ at fewer than $\sqrt{k}$ vertices. Since $P$ has a total of $k$ edges, the length $l$ of the longest uninterrupted portion of $P$ is

$l>\frac{k}{\sqrt{k}}=\sqrt{k}$

Therefore, for some $v_jv_i∈\{v_1,…,v_n\}$, where $j=i+1$, there is a $v_i$$v_j$-path $P_1∈P$ that as at least $\sqrt{k}$ edges. There is also a $v_i v_j$-path $P_2∈C$ of length at least $1$, so $P_2∪P_1$ makes a cycle of at least length $\sqrt{k}$.

$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .