**Exercise from Diestel. **Let be a graph and let be a cycle in . Let . Let be a path from to of length (i.e. number of edges) equal to . Then there exists a path in of length .

**Proof.** Wlog , otherwise we are done. Let and . Let for every and let . Then , hence . Let be such that , then is a cycle of length .**Q.E.D.**.

Advertisements