The Seven Bridges of Konigsberg

Konigsberg was a small town in East Prussia (now Russia), divided by a river into several parts which were connected by seven bridges as shown in the diagram. The citizens of Konigsberg crossed these bridges for leisure walks on Sundays. One day, they wondered, "Can we take a walk in Konigsberg in such a way that we cross each of the seven bridges once and only once?"

At first sight, we seem to be faced with a tedious and daunting task of tracing out all the possible routes with the seven bridges, and showing whether there is a particular route that works. To address such problem more systematically may require techniques of topology and the like. But when Leonhard Euler (1707-1783) looked at the problem, he immediately claimed that it was NOT possible to have such a walk. Despite Euler (pronounced as "oi-ler") was a great mathematician, he was able to prove his claim by a simple and clever way which can be understood by almost anyone. Euler's strategy to tackle the problem was by method of proof by contradiction. Now let's see how the genius was at work:

First note that Konigsberg is divided into FOUR regions, A, B, C and D interconnected by the seven bridges as shown in the diagram. Next assume that it IS possible to have a walk in the town by crossing each of the seven bridges once and only once. The walk may start in any one of the 4 regions, A, B, C or D, and end in any one of them (which may or may not be the starting region). In any case, we must have at least TWO regions which are neither the starting region nor the ending region.
Now consider any one of these regions. Since it is not the starting region nor the ending region, if we go into this region to visit, we must go out from it accordingly. To visit this region once, we have to go into the region through one bridge and out through another since we cannot cross the same bridge more than once. So we have to have 2 bridges connected to this region in order to visit it once. If we visit this region a couple of times, we have to have an even number of bridges so that we don't cross the same bridge more than once. But looking at the diagram, NO region in this town has such a property (i.e. connected with an even number of bridges: the island C has 5 bridges while the other regions A, B and D all have 3 bridges each), let alone there are at least 2 such regions. Hence, our original assumption that it IS possible to have such a walk leads to some contradiction to the given facts, and thus it cannot possibly be true. In other words, we cannot have a walk in Konigsberg by crossing each of the seven bridges once and only once.

Q. E. D.