- Thread starter
- #1

- Thread starter Carl
- Start date

- Thread starter
- #1

- Moderator
- #2

- Feb 7, 2012

- 2,676

Then go through the edges of $E$ one by one in order, starting with the shortest edge $\color{red}e_1$ and finishing with the longest edge $\color{red}e_m$ ... .

At the $k$th stage of this procedure, when you come to the edge $e_k = (u,v)$, the walkers currently at its endpoints $u$ and $v$ change place by walking along $e_k$. If they have not previously moved then that will be the first leg of their walk. But if one or both of them have already moved during a previous stage of the procedure, they will have moved along edges shorter than $e_k$. When the procedure ends (with the walkers at the endpoints of $e_m$ changing places), each walker will have travelled along some increasingly long sequence of edges.At stage $k$ of the procedure, two walkers travel along the edge $e_k$. So the total number of edges travelled during the whole procedure is $2m$. The number of walkers is $n$. So the mean number of edges travelled by a walker is $2m/n$, and therefore at least one of the travellers must have walked along $2m/n$ or more edges.

As the Puzzle Toad site mentions, it is indeed a beautiful proof.

- Thread starter
- #3