Königsberg was a city in Prussia situated on the Pregel River, which served as the residence of the dukes of Prussia in the 16th century. (Today, the city is named Kaliningrad, and is a major industrial and commercial center of western Russia.) The river Pregel flowed through the town, creating an island, as in the following picture. Seven bridges spanned the various branches of the river, as shown.
A famous problem concerning Königsberg was whether it was possible to take a walk through the town in such a way as to cross over every bridge once, and only once. An example of a failed attempt to take such a walking tour is shown below.
OK, so this attempt didn't work. But might there be some other path that would cross every bridge exactly once? This problem was first solved by the prolific Swiss mathematician Leonhard Euler (pronounced "Oiler"), who invented the branch of mathematics now known as graph theory in the process of his solution.
Euler's approach was to regard the spots of land (there are 4 of them) as points to be visited, and the bridges as paths between those points. The mathematical essentials of the map of Königsberg can then be reduced to the following diagram, which is an example of what is called a graph:
For each of the vertices of a graph, the order of the vertex is the number of edges at that vertex. The figure below shows the graph of the Königsberg bridge problem, with the orders of the vertices labeled.
Euler's solution to the problem of the Königsberg bridges involved the observation that when a vertex is "visited" in the middle of the process of tracing a graph, there must be an edge coming into the vertex, and another edge leaving it; and so the order of the vertex must be an even number. This must be true for all but at most two of the vertices--the one you start at, and the one you end at, and so a connected graph is traversible if and only if it has at most two vertices of odd order. (Note that the starting and ending vertices may be the same, in which case the order of every vertex must be even.) Now a quick look at the graph above shows that there are more than two vertices of odd order, and so the graph cannot be traced; that is the desired walking tour of Königsberg is impossible.
Additional Fun with Graphs
1. Suppose the citizens of Königsberg decided to build an eighth bridge, as in the diagram shown below. Would a walking tour of Königsberg now be possible?
A Different Problem with the Same Solution
Euler's solution can also be applied to problems that at first look different from the problem of the Königsberg bridges. Consider the problem of whether it is possible to draw a continuous curve that passes through each of the ten edges (line segments) of the following figure exactly once. (A curve that passes through a vertex is not allowed.)
Can you determine whether it is possible to draw a continuous curve that passes through each of the edges of the following figure exactly once? Now that you know the secret, you can easily make up your own similar challenges.
Graph Theory Today
Today, graph theory is a highly developed field of mathematics, and is both a fertile ground for the creation of new mathematics and an area with many, many applications. Many research problems in graph theory are easily stated and easily understood (although perhaps not easily solved). A few of the applications of graph theory include transportation and warehousing applications, planning and scheduling, analysis of electrical networks, and even understanding the Internet!