Leonard Euler's Solution to the Konigsberg Bridge Problem

Author(s):

Teo Paoletti (The College of New Jersey)

Editor's Note

This article was published in Volume 3 (2006) of Convergence. The following student research report was prepared for Professor Judit Kardos' Math 255 class, held at The College of New Jersey. This was a 3-credit introductory course in the History of Mathematics. This report was counted towards 30% of the final grade. It is an example of the sort of historical research students can do using secondary sources.

Leonard Euler's Solution to the Königsberg Bridge Problem

Königsberg

Our story begins in the 18th century, in the quaint town of Königsberg, Prussia on the banks of the Pregel River. In 1254, Teutonic knights founded the city of Königsberg under the lead of Bohemian King Ottoker II after their second crusade against the Prussians. In the Middle Ages, Königsberg became a very important city and trading center with its location strategically positioned on the river. Artwork from the eighteenth century shows Königsberg as a thriving city, where fleets of ships fill the Pregel, and their trade offers a comfortable lifestyle to both the local merchants and their families. The healthy economy allowed the people of the city to build seven bridges across the river, most of which connected to the island of Kneiphof; their locations can be seen in the accompanying picture [source: MacTutor History of Mathematics Archive].

As the river flowed around Kneiphof, literally meaning pub yard, and another island, it divided the city into four distinct regions. The seven bridges were called Blacksmith’s bridge, Connecting Bridge, Green Bridge, Merchant’s Bridge, Wooden Bridge, High Bridge, and Honey Bridge. According to lore, the citizens of Königsberg used to spend Sunday afternoons walking around their beautiful city. While walking, the people of the city decided to create a game for themselves, their goal being to devise a way in which they could walk around the city, crossing each of the seven bridges only once. Even though none of the citizens of Königsberg could invent a route that would allow them to cross each of the bridges only once, still they could not prove that it was impossible. Lucky for them, Königsberg was not too far from St. Petersburg, home of the famous mathematician Leonard Euler.

Euler and the Bridge Problem

Why would Euler concern himself with a problem so unrelated to the field of mathematics? Why would such a great mathematician spend a great deal of time with a trivial problem like the Königsberg Bridge Problem? Euler was obviously a busy man, publishing more than 500 books and papers during his lifetime. In 1775 alone, he wrote an average of one mathematical paper per week, and during his lifetime he wrote on a variety of topics besides mathematics including mechanics, optics, astronomy, navigation, and hydrodynamics. It is not surprising that Euler felt this problem was trivial, stating in a 1736 letter to Carl Leonhard Gottlieb Ehler, mayor of Danzig, who asked him for a solution to the problem [quoted in Hopkins, 2]:

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. Because of this, I do not know why even questions which bear so little relationship to mathematics are solved more quickly by mathematicians than by others.

Even though Euler found the problem trivial, he was still intrigued by it. In a letter written the same year to Giovanni Marinoni, an Italian mathematician and engineer, Euler said [quoted in Hopkins, 2],

This question is so banal, but seemed to me worthy of attention in that [neither] geometry, nor algebra, nor even the art of counting was sufficient to solve it.

Euler believed this problem was related to a topic that Gottfried Wilhelm Leibniz had once discussed and longed to work with, something Leibniz referred to as geometria situs, or geometry of position. This so-called geometry of position is what is now called graph theory, which Euler introduces and utilizes while solving this famous problem.

Euler's Proof

On August 26, 1735, Euler presented a paper containing the solution to the Konigsberg bridge problem. He addressed both this specific problem, as well as a general solution with any number of landmasses and any number of bridges. This paper, called ‘Solutio problematis ad geometriam situs pertinentis,’ was later published in 1741 [Hopkins, 2]. Euler’s paper is divided into twenty-one numbered paragraphs, and in what follows, a simplified version of Euler’s paragraphs will be presented.

In the first two paragraphs of Euler’s proof, he introduces the Konigsberg Bridge problem. In Paragraph 1, Euler states that he believes this problem concerns geometry, but not the geometry well known by his contemporaries, that involves measurements and calculations, but instead a new kind of Geometry, which Leibniz referred to as Geometry of Position. Then in Paragraph 2, Euler explains to his audience how the Konigsberg problem works. Euler provided a sketch of the problem (see Euler's Figure 1), and called the seven distinct bridges: a, b, c, d, e, f, and, g. In this paragraph he states the general question of the problem, “Can one find out whether or not it is possible to cross each bridge exactly once?”

Euler's Figure 1 from ‘Solutio problematis ad geometriam situs pertinentis,’ Eneström 53 [source: MAA Euler Archive]

After stating the general question he is trying to solve, Euler begins to explore different methods of finding a solution. In Paragraph 3, Euler tells the reader that to solve this specific problem, he could write down all possible paths, but this technique would take a great deal of time, and would not work for larger configurations with more bridges and land masses. Because of these issues, Euler decided to choose a different method for solving this problem.

In Paragraph 4, he begins simplifying the problem by inventing a convenient system to represent the crossing of a bridge. Euler decides that instead of using the lowercase letters to represent the crossing of a bridge he would write the capital letters representing the landmasses. For instance, referencing his Figure 1, AB would signify a journey that started in landmass A, and ended in B. Furthermore, if after traveling from landmass A to B, someone decides to move to landmass D, this would simply be denoted, ABD. In Paragraph 5, Euler continues his discussion on this process explaining that in ABDC, although there are four capital letters, only three bridges were crossed. Euler explains that no matter how many how many bridges there are, there will be one more letter to represent the necessary crossing. Because of this, the whole of the Königsberg Bridge problem required seven bridges to be crossed, and therefore eight capital letters.

In Paragraph 6, Euler continues explaining the details of his method. He tells the reader that if there is more than one bridge that can be crossed when going from one landmass to the other, it does not matter which bridge is used. For example, even though there are two bridges, a and b, that can take a traveler from A to B, it does not matter with Euler’s notation which bridge is taken. In this paragraph, Euler also discusses the specific problem he is dealing with. He explains, using his original figure, that the Königsberg problem needs exactly eight letters, where the pairs of (A,B) and (A,C) must appear next to each other exactly twice, no matter which letter appears first. In addition, the pairs (A,D), (B,D), and (C,D) must occur together exactly once for a path that crosses each bridge once and only once to exist.

Euler's Figures 2 and 3 from ‘Solutio problematis ad geometriam situs pertinentis,’ Eneström 53 [source: MAA Euler Archive]

In Paragraph 7, Euler informs the reader that either he needs to find an eight-letter sequence that satisfies the problem, or he needs to prove that no such sequence exists. Before he does this for the Königsberg Bridge problem, he decides to find a rule to discover whether a path exists for a more general problem. He does this in Paragraph 8 by looking at much simpler example of landmasses and bridges. Euler draws Figure 2, and he begins to assess the situations where region A is traveled through. Euler states that if bridge a is traveled once, A was either where the journey began or ended, and therefore was only used once. If bridges a, b, and c are all traveled once, A is used exactly twice, no matter if it is the starting or ending place. Similarly, if five bridges lead to A, the landmass A would occur exactly three times in the journey. Euler states that, “In general, if the number of bridges is any odd number, and if it is increased by one, then the number of occurrences of A is half of the result.” In other words, if there is an odd number of bridges connecting A to other landmasses, add one to the number of bridges, and divide it by two, to find out how many total times A must be used in the path, where each bridge is used once and only once (i.e. Total Occurrences of A where A has an odd # of bridges = (# of Bridges + 1) / 2 ).

Using this fact Euler solves the Königsberg bridge problem in Paragraph 9. In that case, since there are five bridges that lead to A, it must occur three times (see his Figure 1, above). Similarly, B, C, and D must appear twice since they all have three bridges that lead to them. Therefore 3(for A) + 2(for B) + 2(for C) + 2(for D) = 9, but Euler already stated that there must only be eight occurrences for the seven bridges. This is a contradiction! Therefore, it is impossible to travel the bridges in the city of Königsberg once and only once. The end, or is it? While the people of Königsberg may be happy with this solution, the great mathematician Leonhard Euler was not satisfied. Euler further continues his proof to deal with more general situations.

Euler's Generalization

In Paragraph 10, Euler continues his discussion by noting that if the situation involves all landmasses with an odd number of bridges, it is possible to tell whether a journey can be made using each bridge only once. Euler states that if the sum of the number of times each letter must appear is one more then the total number of bridges, a journey can be made. However, if the number of occurrences is greater than one more than the number of bridges, a journey cannot be made, like the Königsberg Bridge problem. This is because the rule, which Euler gives for an odd number of bridges, using his Figure 2, is true for the general situation whether there is only one other landmass or more than one.

In Paragraphs 11 and 12, Euler deals with the situation where a region has an even number of bridges attached to it. This situation does not appear in the Königsberg problem and, therefore, has been ignored until now. In the situation with a landmass X with an even number of bridges, two cases can occur. The first case is when X is the starting point for the journey. In this case, X will appear twice, once as the starting point, and again as the ending point. In the other case, X is not the starting point. If this were to happen, X would only appear once, as the journey would have to enter through one bridge and immediately leave through the only other one available. Similarly, if there are four bridges attached to X the number of occurrences of X depends on whether or not it is a starting point. If the journey starts in X, it must appear three times, but if it does not begin in X, it would only appear twice. So in general, if X has an even number of bridges attached, then if the journey does not start in X, X appears half the number of times as bridges (i.e. Occurrences of X where X is even and not the starting point = (# of Bridges) / 2). If the journey does start in X then X appears half the number of times as bridges, plus one (i.e. Occurrences of X where X is even and starting point = ((# of Bridges) / 2) + 1).

In Paragraphs 13 through 15, Euler explains how to figure out if a path using each bridge once and only once exists and presents his own example to show how it works. Euler first explains his simple six-step method to solve any general situation with landmasses divided by rivers and connected by bridges. First Euler denotes each landmass with a capital letter. Second, he takes the total number of bridges, adds one, and writes this above the chart he is about to make. Next, he takes the capital letters, puts them in a column, and next to them writes the number of bridges. Fourth, he indicates with asterisks the landmasses which have an even number of bridges. Then, next to each even number, he writes ½ of the number and next to each odd number he places ½ the number plus one. Finally, Euler adds the numbers written in the right-most column and if the sum is one less than, or equal to, the number of bridges plus one, then the required journey is possible. It is important to note however, that if the sum is one less than the number of bridges plus one, then the journey must start from one of the landmasses marked with an asterisk. If the sum is equal to the number of bridges plus one, the journey must start in a region not marked with an asterisk.

Examples

Using the Konigsberg problem as his first example Euler shows the following:

Number of bridges = 7, Number of bridges plus one = 8

Region Bridges Times Region Must Appear

A 5 3

B 3 2

C 3 2

D 3 2

However, 3 + 2 + 2 + 2 = 9, which is more than 8, so the journey is impossible.

Since this example is rather basic, Euler decides to design his own situation with two islands, four rivers, and fifteen bridges. The situation Euler created can be seen in his Figure 3, above. Euler now attempts to figure out whether there is a path that allows someone to go over each bridge once and only once. Euler follows the same steps as above, naming the five different regions with capital letters, and creates a table to check it if is possible, like the following:

Number of bridges = 15, Number of bridges plus one = 16

Region Bridges Times Region Must Appear

A* 8 4

B* 4 2

C* 4 2

D 3 2

E 5 3

F* 6 3

In addition, 4 + 2 + 2 + 2 + 3 + 3 = 16, which equals the number of bridges, plus one, which means the journey is, in fact, possible. Since the sum equals the number of bridges plus one, the journey must start in either D or E. Now that Euler knows it is possible to make a journey, all he needs to do is state what the path will be. Euler chooses the path EaFbBcFdAeFfCgAhCiDkAmEnApBoElD, where he includes which bridges are crossed between the letters representing the landmasses. While this information is extraneous, as the exact bridge does not matter in knowing that a journey is possible, it is useful when selecting a path. This is a good example that shows the method which Euler would use when solving any problem of this nature.

Euler's Conclusions

In the next few paragraphs, Euler presents another way to figure out if a journey can be made given any set of landmasses, bridges, and rivers. In Paragraph 16, Euler points out that the total of the numbers listed directly to the right of the landmasses adds up to twice the total number of bridges. This fact later becomes known as the handshaking lemma. Basically, the handshaking lemma states that each bridge is counted twice, once for each landmass to which it is attached. In Paragraph 17, Euler goes on to state that the sum of all the bridges leading to each region is even, since half of this number is equal to the total number of bridges. However, this is impossible if there are an odd number of landmasses with an odd number of bridges. Therefore, Euler proves that if there are some odd numbers attached to land masses, there must be an even number of these landmasses.

However, this is not enough to prove when there is a path where each bridge is used once and only once, as the Königsberg Bridge problem has an even number of landmasses with an odd number of bridges going to them. Because of this, Euler adds more restrictions in Paragraphs 18 and 19. Euler explains that since the total of the numbers of bridges attached to each landmass is equal to twice the number of bridges (as seen in the handshaking lemma), so therefore if you add two to this sum and then divide by two, you will get the number of total bridges plus one. This number is the same as the one used before, which is used to tell if a path is possible. If all the numbers are even, then the third column in the table will sum to one less than the total number of bridges plus one.

Euler then explains that it is obvious that if there are two landmasses with an odd number of bridges then the journey will always be possible if the journey starts in one of the regions with an odd number of bridges. This is because if the even numbers are halved, and each of the odd ones are increased by one and halved, the sum of these halves will equal one more then the total number of bridges. However, if there are four or more landmasses with an odd number of bridges, then it is impossible for there to be a path. This is because the sum of the halves of the odd numbers plus one along with the sum of all of the halves of the even numbers will make the sum of the third column greater than the total number of bridges plus one. Therefore, Euler just proved that there can be at most two landmasses with an odd number of bridges.

With this being stated, Euler can now make his conclusions concerning more general forms of the Königsberg Bridge problem. In Paragraph 20, Euler gives the three guidelines that someone can use to figure out if a path exists using each bridge once and only once. First, he claimed if there are more than two landmasses with an odd number of bridges, then no such journey is possible. Second, if the number of bridges is odd for exactly two landmasses, then the journey is possible if it starts in one of the two odd numbered landmasses. Finally, Euler states that if there are no regions with an odd number of landmasses then the journey can be accomplished starting in any region. After stating these three facts, Euler concludes his proof with Paragraph 21, which simply states that after one figures out that a path exists, they still must go through the effort to write out a path that works. Euler believed the method to accomplish this was trivial, and he did not want to spend a great deal of time on it. However, Euler did suggest concentrating on how to get from one landmass to the other, instead of concentrating on the specific bridges at first.

Euler's Proof and Graph Theory

When reading Euler’s original proof, one discovers a relatively simple and easily understandable work of mathematics; however, it is not the actual proof but the intermediate steps that make this problem famous. Euler’s great innovation was in viewing the Königsberg bridge problem abstractly, by using lines and letters to represent the larger situation of landmasses and bridges. He used capital letters to represent landmasses, and lowercase letters to represent bridges. This was a completely new type of thinking for the time, and in his paper, Euler accidentally sparked a new branch of mathematics called graph theory, where a graph is simply a collection of vertices and edges. Today a path in a graph, which contains each edge of the graph once and only once, is called an Eulerian path, because of this problem. From the time Euler solved this problem to today, graph theory has become an important branch of mathematics, which guides the basis of our thinking about networks.

The Königsberg Bridge problem is why Biggs states [Biggs, 1],

The origins of graph theory are humble, even frivolous. . . . The problems which led to the development of graph theory were often little more than puzzles, designed to test the ingenuity rather than the stimulate the imagination. But despite the apparent triviality of such puzzles, they captured the interest of mathematicians, with the result that graph theory has become a subject rich in theoretical results of a surprising variety and depth.

As Biggs' statement would imply, this problem is so important that it is mentioned in the first chapter of every Graph Theory book that was perused in the library.

After Euler’s discovery (or invention, depending on how the reader looks at it), graph theory boomed with major contributions made by great mathematicians like Augustin Cauchy, William Hamilton, Arthur Cayley, Gustav Kirchhoff, and George Polya. These men all contributed to uncovering “just about everything that is known about large but ordered graphs, such as the lattice formed by atoms in a crystal or the hexagonal lattice made by bees in a beehive [ScienceWeek, 2].” Other famous graph theory problems include finding a way to escape from a maze or labyrinth, or finding the order of moves with a knight on a chess board such that each square is landed on only once and the knight returns to the space on which he begun [ScienceWeek, 2]. Some other graph theory problems have gone unsolved for centuries [ScienceWeek, 2].

The Fate of Königsberg

While graph theory boomed after Euler solved the Königsberg Bridge problem, the town of Königsberg had a much different fate. In 1875, the people of Königsberg decided to build a new bridge, between nodes B and C, increasing the number of links of these two landmasses to four. This meant that only two landmasses had an odd number of links, which gave a rather straightforward solution to the problem. The creation of the extra bridge may or may not have been subconsciously caused by the desire for a path to solve the town’s famous problem.

However, a new bridge did not solve all of Königsberg's future problems, as the town did not expect back in the nineteenth century, “the sad and war-torn fate that awaited it as host for one of the fiercest battles of WWII.” During four days in August 1944, British bombers destroyed both the old town and the northern parts of Königsberg. In January and February 1945, the region surrounding Königsberg was surrounded by Russian forces. German civilians began to evacuate from the town, but move too late. Thousands of people are killed trying to flee by boat and on foot across the icy waters of the Curonian Lagoon. In April 1945, the Red Army captured Königsberg with about ninety percent of the old town lying in ruins.

A current street map of Königsberg is provided below [source: MacTutor History of Mathematics Archive]. This map shows how much the town has changed. Many of the bridges were destroyed during the bombings, and the town can no longer ask the same intriguing question they were able to in the eighteenth century. Along with a greatly different layout, the town of Königsberg has a new name, Kaliningrad, with the river Pregel renamed Pregolya [Hopkins, 6]. While the fate of Königsberg is terrible, the citizens' old coffeehouse problem of traversing each of their old seven bridges exactly one time led to the formation of a completely new branch of mathematics, graph theory.