The East Prussian city of Königsberg (now part of Russia and known as Kaliningrad) straddles both banks of the River Pregel and an island, called Kneiphof, located right where the river divides into two branches. In the 18th century, seven bridges spanned various segments of the river, connecting different parts of the city.
These bridges were the subject of a well-known puzzle at the time: Could a person follow a path through the city that crosses each of the bridges only once, then returns to the starting point?
In 1735, Leonhard Euler (1707–1783), then living in St. Petersburg, provided the first mathematical proof that such a journey is impossible. He presented it to members of the St. Petersburg Academy on Aug. 26 of that year. His solution was eventually published in 1741 in the academy’s proceedings, under the title “Solutio problematis ad geometriam situs pertinentis (The solution of a problem relating to the geometry of position).”
“Backlogs were apparently a problem even in the 18th century, but perhaps they were more of a problem for Euler than most since he was so prolific,” comments Gerald K. Alexanderson of Santa Clara University in the October Bulletin of the American Mathematical Society. Indeed, within the mathematics section of the 1741 volume, 11 of the 13 articles are by Euler, all written in 1735 or 1736.
Euler’s paper arguably marks the beginning of topology and graph theory. Even the paper’s title shows that Euler himself was aware that he was dealing with a new type of geometry in which distance and measurement are not relevant. What matters is position and connection.
In his paper, Euler not only explained why it’s impossible to make the desired journey across the Königsberg bridges but also established criteria for determining whether such a journey is possible for any network of bridges anywhere.
He proposed the following method for solving a given arrangement of water and bridges.
- Denote by the letters A, B, C, and so on, the various areas that are separated from one another by water.
- Take the total number of bridges, add one, and note this sum.
- Write the letters A, B, C, and so on, in a column, and write next to each the number of bridges leading to it.
- Indicate with an asterisk those letters that have an even number next to them.
- Next to each even one, write half the number, and next to each odd one, write half the number increased by one.
- Add together these last numbers. If this sum is less than, or equal to, the noted sum (the number of bridges plus 1), conclude that the desired journey is possible.
Euler added that, if the sum is one less that the noted number, the journey must begin from one of the areas marked with an asterisk, and it must begin from an unmarked one if the sum is equal.
Euler applied his method to the Königsberg bridges (figure 1, below), then to a second configuration with two islands, six land masses, and 16 bridges (map shown below as Euler’s figure 3).
Here’s the table that results:
15 + 1 = 16 |
||
A* |
8 |
4 |
B* |
4 |
2 |
C* |
4 |
2 |
D |
3 |
2 |
E |
5 |
3 |
F* |
6 |
3 |
16 |
Euler concluded that the desired journey can be made if it starts from area D or E.
He then went on in his paper to develop simplified rules for determining whether a bridge-crossing problem has a solution. For a complete, step-by-step account of Euler’s arguments, written by Janet Heine Barnett of the University Colorado-Pueblo, see http://www.math.nmsu.edu/hist_projects/Euler-Barnett.pdf.
The Königsberg bridge problem can be simplified by representing each of the four land masses as a point and each bridge as a line (or arc). Anyone standing on any given land mass would have to have a way to get on and off. So, each land mass would require an even number of bridges. However, in Königsberg, each land mass has an odd number of bridges. As a result, all seven bridges can’t be crossed without crossing one of them more than once.
Representation (above) of the Königsberg bridge problem as a graph of points and lines (vertices and edges). Solving the problem would require drawing this diagram without retracing any line or picking up your pencil.
The problem can be solved, however, if you add or remove one bridge. Does it matter which bridge you remove or where you add a bridge?
Nowadays, two of the Königsberg bridges no longer exist, and a single bridge has replaced a pair of the bridges that cross from one side of the river to the other via the island. A set of stairs in the middle of this bridge allows you to visit or leave the island (see http://www.matheory.info/konigsberg/). If you start on the island, it’s now possible to find a route that covers all the bridges, as desired in the original problem.
Interestingly, as Alexanderson points out, Euler was initially skeptical that mathematics was required for solving the original problem.
In an earlier letter to Carl Leonhard Ehler, mayor of Danzig, Euler had complained that the Königsberg problem “bears little relationship to mathematics . . . for the solution is based on reason alone, and its discovery does not depend on any mathematical principle.”
But, further thought led Euler to a mathematical solution and a pioneering paper in topology.
