Changes

==== The Bridges of Konigsberg ====

==== The Bridges of Konigsberg ====

The earliest roots of the modern study of topology (and [[graph theory]] in particular) lie in [[Leonhard Euler]]'s investigations of a famous puzzle from the 1730s.  The town of Konigsberg (now [[Kaliningrad]]) was bisected by a river, which contained two large islands.  There were seven bridges connecting the islands, as indicated in the accompanying image.  The problem asked for a walk through the town which would cross each bridge exactly once: every bridge must be crossed once, and none more than once.

The earliest roots of the modern study of topology (and [[graph theory]] in particular) lie in [[Leonhard Euler]]'s investigations of a famous puzzle from the 1730s.  The town of Konigsberg (now [[Kaliningrad]]) was bisected by a river, which contained two large islands.  There were seven bridges connecting the islands, as indicated in the accompanying image.  The problem asked for a walk through the town which would cross each bridge exactly once: every bridge must be crossed once, and none more than once.

Euler proved that no such path existed, with the following simple and elegant argument: observe that the path one takes while on the islands is irrelevant to the problem at hand, and that all that matters is the order in which the bridges are traversed.  Every time one enters one landmass by means of a bridge, he leaves it by means of another.  This means that the number of bridges entering and exiting each landmass must be even, except possibly the landmass in which he starts and the one in which he ends (since he does not both enter and exit these).  However, in Konigsberg, each of the four landmasses is served by an odd number of bridges!  This means that no tour of the sort desired is possible.

Euler proved that no such path existed, with the following simple and elegant argument: observe that the path one takes while on the islands is irrelevant to the problem at hand, and that all that matters is the order in which the bridges are traversed.  Every time one enters one landmass by means of a bridge, he leaves it by means of another.  This means that the number of bridges entering and exiting each landmass must be even, except possibly the landmass in which he starts and the one in which he ends (since he does not both enter and exit these).  However, in Konigsberg, each of the four landmasses is served by an odd number of bridges!  This means that no tour of the sort desired is possible.