Mr. Toad lives on a vertex of a 3-regular planar graph. He decides to take a walk along the edges of the graph. He has no sense of direction but he can tell left from right. He decides that he will alternately take the left edge and then the right edge when he comes to the next vertex. Show that he will he eventually get back home.
More puzzles: http://www.cs.cmu.edu/puzzle/