Description: This seminar was given by me and my group partner Dev Agarwal on November 20, 2003:
Historical Problem:
In the town of Koenigsberg there was a river with two islands and seven bridges.
Each Sunday people would go for a walk, and after a while someone noticed that no matter where they started they were never able to cross each bridge once and only once during their walk. It seemed that no matter where they started and where they walked, they would always end up in the wrong place for crossing that last bridge.
Euler`s Solution :
Euler demonstrated the main ideas found in all mathematics:
(1) Abstraction: The first thing that Euler did was to say that several things didn't matter. The shapes of the islands, the lengths of the bridges, the distances between the bridges, and so on. He threw away these details and ended up with a simpler diagram.
(2) Reasoning: There are four meeting places and all of them will have to be visited on our walk. You might start at one and finish at another, but there will always be at least two of them that are neither start nor finish. Let's pick one to think about, we'll call it X. Since X has some bridges coming to it we will have to visit it at least once. Since we neither start nor finish there, every time we come in we must go out again, and on a different bridge. That means that the total number of bridges that land at X must be even. For every in there is an out and if there's an odd number of bridges, that won't work.
So X our place that is neither start nor finish, must have an even number of bridges. However, all our landing places have odd numbers of bridges,and that makes it impossible to do our walk.
(3) Generalisation: No diagram can be drawn if it has more than two places with an odd number of lines. If a diagram does have two places with an odd number of lines, then one of them must be the start and the other must be the end.
Note: This analysis by Euler created the subject of Graph Theory. The "diagrams" are now called graphs, the "places" are now called vertices and the "lines" are now called edges. |