CHAPTER 11
A STROLL THROUGH KÖNIGSBERG
In order to place Euler’s formula in a modern context, we must discuss a mathematical field called graph theory. This is not the study of graphs of functions that we encountered in high school precalculus (y = mx + b is a line, y = x2 is a parabola, and so on.). It is the study of graphs such as those shown in figure 11.1. They are made of points, called vertices, and lines joining these points, called edges.*
In 1736, during his first stay in St. Petersburg, Euler tackled the now famous problem of the seven bridges of Königsberg. His contribution to this problem is often cited as the birth of graph theory and topology.
The city of Königsberg was founded by the Teutonic Knights in 1254. At that time it was located in Prussia, near the Baltic sea, on a fork in the River Pregel. Later it became the capital of East Prussia. The city, which was heavily damaged by Allied bombing during World War II, fell under Soviet control following the Potsdam agreement. There were many changes in Königsberg after it became a Soviet state—most of the native Germans were expelled, the name of the city was changed to Kaliningrad, and the river was renamed the Pregolya. Today Kaliningrad is part of Russia and is the capital of the Kaliningrad Oblast region. Kaliningrad Oblast has the unique distinction that it is not connected to the rest of Russia; it is surrounded by Poland, Lithuania, and the Baltic Sea. Unlike cities such as Stalingrad and Leningrad, Kaliningrad has not reverted to its pre-Communist name. The most famous resident of Königsberg was the eighteenth century philosopher Immanuel Kant (1724–1804). Also from Königsberg came Christian Goldbach, the mathematician to whom Euler announced the discovery of his polyhedron formula.
Figure 11.1. Graphs.
The city is located on a fork in the river, and sitting in the middle of the river, near the fork, is Kneiphof Island. In Euler’s time, there were seven bridges crossing the river joining the various banks and the island (see figure 11.2). As the story goes, the residents of Königsberg would leisurely walk around their city and entertain themselves by attempting to cross each of the seven bridges exactly once. No one was able to find such a route. This supposed pastime became the bridges of Königsberg problem:
Is it possible for a pedestrian to walk across all seven bridges in Königsberg without crossing any bridge twice?
It is not known how Euler learned of this problem. Perhaps he heard it from his friend Carl Ehler, the mayor of Danzig, Prussia, who corresponded with Euler on behalf of a local professor of mathematics. We have letters between Ehler and Euler during the period 1735–1742, some of which discuss the Königsberg bridge problem. We do know that initially Euler was indifferent. In 1736, in a letter to Ehler, Euler wrote:
Thus you see, most noble Sir, how this type of solution bears little relationship to mathematics, and I do not understand why you expect a mathematician to produce it, rather than anyone else, for the solution is based on reason alone, and its discovery does not depend on any mathematical principle.2
Eventually, Euler spent time thinking about the problem. The same feature that at first turned him off eventually piqued his interest: the problem did not fit comfortably within the existing mathematical framework. He realized that the matter seemed geometrical, yet there was no need for exact distances. Information about relative positions was all that was needed.
Figure 11.2. The seven bridges of Königsberg.
Another letter from 1736, this one written to the Italian mathematician and engineer Giovanni Marinoni (1670–1755), said:
This question is so banal, but seemed to me worthy of attention in that geometry, nor algebra, nor even the art of counting was sufficient to solve it. In view of this, it occurred to me to wonder whether it belonged to the geometry of position, which Leibniz had once so much longed for.3
Figure 11.3. The graph associated with the bridges of Königsberg problem.
In this letter Euler used a term coined by Leibniz, geometriam situs, which translates to geometry of position. Later this term would become analysis situs (analysis of position), and eventually, topology. Leibniz was referring to a new field in mathematics, one that “deals directly with position, as algebra deals with magnitudes.”4 There is some disagreement among scholars whether Euler misunderstood Leibniz’s use of this term; nevertheless, Euler agreed with Leibniz’s recognition of the need for new mathematical techniques to handle this situation.
In 1736 Euler presented his paper “Solutio problematis ad geometriam situs pertinentis” (“The solution of a problem relating to the geometry of position”) to the St. Petersburg Academy.5 It was published in 1741. In it Euler solved the Königsberg bridge problem and, in his typical style, generalized his solution to any layout.
Euler realized that the only important details in the problem are the relative locations of the land masses and the bridges joining them. Using a diagram, we can abstract the situation easily and elegantly. Place a vertex on each piece of land (one on each of the three banks and one on the island), and join each pair of vertices by as many edges as there are bridges connecting the landmasses. The resulting graph is shown in figure 11.3.
In this way, we reduce the problem to one about a graph—i.e., is it possible to trace this graph with a pencil without lifting the pencil and without redrawing any edge? From this example we can formulate the more general question: how do we determine if we can trace a given graph in this way?
It is a common misconception that the Königsberg graph, shown in figure 11.3, is found in Euler’s paper. In reality, neither the Königsberg graph nor any other graph appears there. Graph tracing developed independently of the Königsberg bridge problem. Graph tracing puzzles first appeared in the early nineteenth century, both in mathematical articles and in books of recreational mathematics. It was not until 1892 that W. W. Rouse Ball (1850–1925), in his popular work Mathematical Recreations and Problems,6 made the connection between Euler’s result on the bridges of Königsberg and graph tracing. The first appearance of the Königsberg graph was in Ball’s book, over a hundred and fifty years after the publication of Euler’s paper.
It is also common to cite Euler’s paper as the genesis of graph theory. This attribution is not unreasonable. Although Euler never drew a graph in his paper, his abstract treatment of the problem resembles the graph theory argument. His application of geometriam situs, what would later be called topology, to the problem and his recognition of the novelty of this method signals the start of this new field.
In order to discuss his solution we need a few definitions. As with polyhedra, the degree of a vertex is the number of edges emanating from it. If there is a loop at this vertex (an edge starting and ending at the vertex, such as in the right graph in figure 11.1), then the loop contributes two to the degree. The graph for the bridges of Königsberg problem has three vertices of degree 3 and one vertex of degree 5. A graph is connected if it is possible to get from any vertex to any other vertex by following a sequence of edges.
A tracing of a graph that begins at one vertex and ends at another vertex is called a walk. We are interested in a very special class of walks, ones that visit each edge exactly one time: this is called an Euler walk. If the Euler walk begins and ends at the same vertex, then it is called an Euler circuit. In general, a circuit is a walk along a graph that starts and ends at the same vertex and never visits the same edge twice. A (non-Eulerian) circuit may not visit every edge.
Using the language of graph theory, we recast the bridges of Königsberg problem as follows.
Does the bridges of Königsberg graph (figure 11.3) have an Euler walk? More generally, how do we determine if a graph has an Euler walk?
Euler solved both of these problems. Translated in to modern language, it is stated as follows.
A graph has an Euler walk precisely when it is connected and there are zero or two vertices of odd degree. If there is a pair of vertices of odd degree, then the walk must start at one of these vertices; otherwise the walk may begin anywhere.
Using these criteria we easily solve the bridges of Königsberg problem. Because the graph has four vertices of odd degree, there is no Euler walk! It is no wonder that the residents of Königsberg were so frustrated in their search for the ideal afternoon stroll.
But why is Euler’s solution true? The requirement that the graph be connected is obvious. The insistence that the graph have zero or two vertices of odd degree requires some thought. To prove the theorem, we have two objectives. First we must show that any graph with an Euler walk must have zero or two vertices of odd degree. Then we must show the converse: if a connected graph has zero or two vertices of odd degree, then it has an Euler walk.
Suppose we have a graph with an Euler walk; we will show that it must have zero or two vertices of odd degree. Place a sheet of tracing paper on top of the graph and proceed to trace the Euler walk. As we begin tracing the Euler walk, the first vertex will have degree one, and all other vertices will have degree zero. As we get to, and trace through, the second vertex, it will have degree two. From then on, each time we pass a vertex, the degree increases by two. This continues until we reach the end of the walk. At this point, we add one to the degree of the last vertex. If the walk starts and ends at two different vertices, then these two vertices will have odd degree, and they will be the only vertices of odd degree. If the walk starts and ends at the same vertex, then it, and all other vertices, will have even degree.
Euler took the converse for granted: if a graph has zero or two vertices of odd degree, then it has an Euler walk. The first demonstration of this fact was given by Carl Hierholzer (1840–1871), and was published posthumously in 1873.7
Begin with a connected graph having either zero or two vertices of odd degree. If the graph has a pair of vertices of odd degree, then place the pencil at one of these vertices; otherwise put it at any vertex. Begin tracing in any direction. Upon reaching the first vertex, choose randomly a new edge to follow. Continue in this way, making arbitrary choices at each vertex (while avoiding edges that were previously visited, of course), until it is impossible to go any farther. By the argument given earlier, if we began at a vertex of odd degree, then the end of this tracing will be at the other vertex of odd degree; otherwise the tracing will end at the starting vertex. In figure 11.4 path abcdefghi is such a walk.
Figure 11.4. Building an Euler walk.
If this path does not pass through every edge in the graph, then remove all of the traced edges and look at the remaining graph (it may no longer be connected). Place your pencil at a vertex that was in your original tracing. As before, trace this graph until it is impossible to trace any farther. In our example, we obtain the walk jkl. Now insert this new tracing into the appropriate location of the walk that you constructed previously. In our example, we may insert jkl between edges b and c of the original walk. So, we obtain abjklcde fghi, which is an Euler walk. In general, it may be necessary to make several such insertions before all edges are traced.
Notice that we learned more about graph tracing than is evident in the solution given above. Our discussion was aimed at finding Euler walks, but we also determined when the walk can begin and end at the same vertex.
Figure 11.5. A new bridge in Königsberg and the new graph.
That is:
A graph has an Euler circuit precisely when it is connected and has no vertices of odd degree. In this case, the Euler circuit can begin and end at any vertex.
In 1875, a century and a half after Euler analyzed the walking routes of the city of Königsberg, the city built a new bridge.8 It was erected west of Kneiphof Island from the northern bank to the southern bank (see figure 11.5). With this in place, the residents of Königsberg could finally take a stroll across all the bridges and visit each bridge exactly one time, for there were now exactly two vertices of odd degree—the vertices corresponding to the island and the land between the fork. Of course, some of the townsfolk were not able to begin their walk at their front doorstep, and no one was able to end his or her walk where it began.
This solution to the Königsberg bridge problem illustrates a general mathematical phenomenon. When examining a problem, we may be overwhelmed by extraneous information. A good problem-solving technique strips away irrelevant information and focuses on the essence of the situation. In this case details such as the exact positions of the bridges and land masses, the width of the river, and the shape of the island were extraneous. Euler turned the problem into one that is simple to state in graph theory terms. Such is the sign of genius.
Figure 11.6. Listing’s graph-tracing puzzle.
Figure 11.7. An incorrect solution to the brick wall puzzle.
We conclude with three examples. In 1847, Johann Benedict Listing (18081882), a mathematician whom will meet again later, produced the graph shown in figure 11.6 to illustrate the tracing problem (we draw the graph as Listing did and omit the vertices at the intersections).9 Does it have an Euler walk? Does it have an Euler circuit? The reader may wish to think about this problem before proceeding.
We see that every vertex has even degree except for the left-most and right-most—these vertices have degree five. Because there are exactly two vertices of odd degree, Listing’s graph does have an Euler walk, and every Euler walk must begin at one of these vertices and end at the other. Because the graph has vertices of odd degree, there is no Euler circuit.
The second example is a variation on the bridge problem. Consider the drawing resembling a brick wall shown in figure 11.7. Is it possible to draw a single unbroken curve that crosses each of the line segments in the figure exactly one time (the curve may begin and end in different bricks)? The attempt shown on the right is not a valid solution because there is one uncrossed segment.
It is not possible. We can justify this claim by transforming the problem into a graph-tracing problem. Place one vertex inside each brick and one vertex outside the figure. Draw one edge from a vertex to another vertex for each segment separating the corresponding bricks in the original picture (see figure 11.8). It suffices to determine whether this graph has an Euler walk. Because the graph has four vertices of degree five, it has no Euler walk. So there is no curve with the desired properties.
Figure 11.8. A graph associated with the brick wall puzzle.
Figure 11.9. A typical game of dominoes.
Finally, we apply graph theory and Euler walks to the game of dominoes. This example was concocted by Orly Terquem (1782–1862) in 1849.10 In a standard set of dominoes, each half of a domino has zero to six pips. No two dominoes in the set are alike, and every combination is present in the set. This gives a total of 28 dominoes. Play alternates as each player lays down a domino in such a way that the number on half of her domino abuts the same number on an existing domino. A domino with the same number of pips on each half can be placed in a T formation against a tile with that number of pips on one half (see figure 11.9). Play ends when a player is unable to lay down another domino. We ask, will a game always end with a player holding dominoes in his cache? Or is it possible to lay down all of the dominoes and never get stuck?
To analyze this problem we create a graph as follows. Start with seven vertices labeled 0 through 6. Each domino corresponds to an edge on this graph. A domino with m pips on one half and n pips on the other becomes an edge from vertex m to vertex n. Putting all of the dominoes on the graph we obtain figure 11.10. Notice that there is a loop at each vertex corresponding to dominoes with the same number of pips on each half.
Figure 11.10. The graph corresponding to the collection of all domino tiles.
Figure 11.11. Part of a game of dominoes in which every tile is played, and the corresponding graph.
Each vertex in the domino graph has degree eight. Because the degree of every vertex is even, this graph has an Euler walk. So, we can trace the entire graph passing through each edge exactly one time. This observation is the key to answering our question. To show that we can play all of the dominoes, it suffices to find one configuration that achieves this end. The one we produce is simple (although it would be unlikely to arise in actual play)—a line of dominoes.
Start with the first edge in the Euler walk. Suppose it joins vertices 0 and 3. Lay down the domino containing zero pips and three pips. Now consider the second edge in the walk. We know that this edge must begin at vertex 3. Suppose the edge joins vertices 3 and 1. We then lay down the domino with three pips and one pip on the end of the previous domino (see figure 11.11). We continue on in this fashion, laying down tiles as we go. Because we are following an Euler walk, we will get each edge exactly one time. Thus we will be able to lay down every domino in the set.
As these examples show, graph theory has some wonderful applications to recreational mathematics. However, it is also a very important field of mathematics that has numerous practical applications in such diverse areas as computer science, networking, social structures, transportation systems, and epidemiological modeling. We will see graph theory again in the chapters that follow. In particular, we will create an analogue of Euler’s formula for a certain class of graphs.
* Sometimes graphs are called networks, with the vertices and edges called nodes and links, respectively.