Königsberg Bridges

In the 1700s, the city of Königsberg, in Prussia (now Kaliningrad, Russia) had seven bridges (shown in red below) across two branches of the Pregel River, connecting an island in the river, called Kneiphof, with land on each side of each branch of the river, as shown below:

A tradition had developed among the city's residents of taking a Sunday stroll while attempting to cross each bridge once and only once. It was considered an interesting amusement, but no-one could seem to accomplish the task.

In 1736, Leonhard Euler learned of the Königsberg bridge problem, approached it from a mathematical standpoint, and presented a paper to the Russian Academy, the importance of which went well beyond this specific problem. Euler transformed the problem into what is called a graph (as on the right), with each part of the city being a vertex or a node on that graph and each bridge being an edge or a link.

Now, the problem boils down to whether there is a path on the graph that traverses each edge once and only once. Think about it for a second. Say that there is such a traversal. Every time you enter a node, you will have to exit that node (except for the starting and ending nodes). So, if such a path exists, no more than two nodes can have an odd number of connected edges. However, all four vertices have an odd number of connected edges. Therefore, it isn't possible to find a path that traverses each edge exactly once, and so it isn't possible to cross each of the Königsberg bridges exactly once.

You might be interested in the subsequent history of Königsberg and its bridges. By the twentieth century, an eighth bridge had been built, to the east of Kneiphof Island, as shown in green below:

With this eighth bridge, there were now only two odd vertices, so it was possible to cross each bridge exactly once, as long as you didn't mind ending up somewhere different from where you started. During World War II, Königsberg was devastated and its population forcibly removed. Today, of the original bridges, only the westernmost three bridges survive, and a new bridge has been built to connect the north bank of the Pregel River to the south bank, bypassing Kneiphof Island entirely.

Sources used (see bibliography page for titles corresponding to numbers): 33, 34, 63.