MHB Can You Explain the Puzzle Toad Proof?

[Carl1]

 

[Opalg]

It would be easier to understand that proof if the second sentence was made more explicit:

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$[/color] ... .​

​

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 traveled 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 traveled during the whole procedure is $2m$. The number of walkers is $n$. So the mean number of edges traveled 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.

 

[Carl1]

Thank you so much. Now I understand the proof. It is beautiful.