# Paths from cycles

Exercise from Diestel. Let $G$ be a graph and let $C$ be a cycle in $G$. Let $u,v\in C$. Let $P$ be a path from $u$ to $v$ of length (i.e. number of edges) equal to $k$. Then there exists a path in $G$ of length $\geq$ $\sqrt{k}$.

Proof. Wlog $|C|<\sqrt{k}$, otherwise we are done. Let $P\cap C :=\{v_0, \ldots, v_n\}$ and $n < \sqrt{k}$. Let $P_i:=v_i P v_{i+1}$ for every $0\leq i\leq n-1$ and let $m:=max_{i} \{|P_i|\}$. Then $k=\sum_{i=0}^{n} |P_i| \leq \sum_{i=0}^{n} m = mn < m\sqrt{k}$, hence $m>\sqrt{k}$. Let $j$ be such that $|P_j|=m$, then $v_j P v_{j+1} C v_j$ is a cycle of length $l\geq m+1 > \sqrt{k}+1$.Q.E.D..