Sunday Afternoon Fun

I spent a glorious afternoon playing the "can you sketch this picture without lifting your pencil?" game with my daughter. We started with a few standard ones that you can find with a simple Google Image search like:

click on image to enlarge

Soon enough, we just started making up random pictures for each other.

After a while, I told her the first part of the secret (Euler Paths), which tells you whether a solution exists.

• identify all the points (nodes)
• write down the number of lines that meet at each node
• scratch off nodes with an even number number of lines
• count the number of (remaining) "odd" nodes
• if this number is 0 or 2, then it is possible to solve the problem

As an example the following figure,

has 3 even nodes (2, 4, and 2), and 2 odd nodes. Thus, it is possible to sketch this "graph" without lifting your pencil.

Showing existence is only the first part, but the second part is an algorithm to actually solve the problem, once you know it is solvable.

Wikipedia lists two methods (both of which are over a century old): Fleury's and Hierholzer's algorithms. But for "kiddie problems" a simpler rule of thumb works in most cases:

So this is the second secret: start from an odd node! For most cases, there are multiple solutions, and it is hard to go wrong with this simple "suggestion"!

PS: If the number of odd nodes is 0, it doesn't matter where you start, and your start and finish points are exactly the same!