Tuesday, June 9, 2015

Pencil Puzzles Series #2

Euler proved that you could not cross all seven bridges without doubling back, or in terms of a pencil puzzle, without lifting the pencil from the paper. The seven bridge puzzle looks like this:

When drawn out as vertices and edges. Euler was able to prove that the parity (odd or even) of the vertices is what is important to whether you can draw a figure without lifting the pencil or duplicating an edge. Each vertex (or blue spot) has a number of edges (or lines) going from it. If the number of edges is even, the vertex is called even. If the number of edges is odd, the vertex is called odd. In the above figure, the vertices have 5,3,3 and 3 lines, so all four vertices are odd.

Euler was able to prove that the only graphs (or figures) you can draw without lifting the pencil are graphs with zero or two odd vertices. If there are two odd vertices you must start drawing on one and end on the other.

So which of the figures A,B,C and D can be drawn without lifting the pencil?

Bonus:
You can draw a continuous line that passes through all the vertices every time. This is called a simple path.
If you can draw a continuous line that covers all the edges it is called an Euler path.