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
6 comments:
v interesting indeed. there was a further complicated variant of the puzzle. one which had curves on four sides of the square (here its on only one side) but i dont think that can be drawn without lifting the pencil
Yeah, in the variant you speak about, there would be 5 edges emanating from each node and so by Euler's theorem, we wont be able to draw it without lifting the pencil.
Onkar... this is a nice post. We used try the similar puzzle, but all four sides of the square have the semi-circular connection. Though that was impossible to solve, we used to fold the paper, and cheat to solve it.
Now that we have expanded brains, the logic is simple that, each intermediate node has to have even number of edges connected to it, because once you enter, you have to exit that node!
I guess, Euler has the most logical brain ever. Who knows... some decades later, somebody like you may write a post "...and the world lost an Onkar" ;-)
i remember how this problem had fascinated me when i was being introduced to graph theory! :) nice post...reminded me of good ol' days!
http://en.wikipedia.org/wiki/Seven_Bridges_of_K%C3%B6nigsberg
Good God! Otherwise, we would have another mathematical constant o: Onky's number... I mean, Onky is numb.. er... Without doubt, because of the irrational nature of Onky's thoughts, o would have been irrational. Also, because of Onky's inexplicable beliefs in transcendentalism, o would have been transcendental. And we would've had more trouble. Hence proved.
@Suneel: Let's take a leap of faith.
Post a Comment