Euler, the legendary mathematician went to the city of Konigsberg. The city was divided in four parts by rivers. The rivers had seven bridges on it. There he was asked if it was possible to travel all the bridges in a single journey without going twice over any bridge.
Euler realized that it was simply not possible !
He redrew the graph drawing edges for each bridge.
He said that traveling each bridge exactly once is same as drawing the graph without lifting pencil. Then he generalized the problem saying that drawing any graph without lifting pencil such that you start from point X (source) and end at point Y (destination) is possible if and only if each point (technically "node") had even number of edges connected to it, with possible exceptions of X and Y.
I had read about this long back but few days ago I tried to prove it and finally proved it. But proving it reminded me of my childhood days.
Someone at my school, mostly a classmate gave us a puzzle. We had to draw the figure below without lifting pencil.
I solved it after a few attempts. It turns out that you must start from point A and end at point B (or vice versa). Because Euler's theorem tells us that only source (A) and destination (B) are allowed to have odd number of edges connected to them, but every intermediate node must have even number of edges.
In my schooldays puzzle, only A and B had odd number of edges. So if your starting and end points of journey were not these points, it is impossible to draw the figure without lifting the pencil.
Though I solved that puzzle, I never realized that it was not the answer but the nature of question that was important.
But I never thought it that way.... and the world lost an Euler ! :P :P
