In this article, we introduce Eulerian walks (or paths), directed graphs, the Königsberg bridge problem and give an example of how mathematician Leonhard Euler stumbled upon a new area of mathematics.

Leonhard Euler crosses the seven bridges of Königsberg

The beauty of taking a walk without any distractions is that not only your feet but also your thoughts start to wander off. It is possible to completely lose yourself in the depths of your own mind. It is, in fact, a pretty great way to come up with solutions for unsolved problems. That may be one of the reasons why mathematicians are famous for taking long walks to contemplate ideas. This is the story of such a walk and the mathematician that went for it. I am of course talking about Leonhard Euler who walked around Königsberg and noticed something interesting.

Before we discuss the thing that Euler noticed, we should first introduce the man himself. He is considered to be one of the greatest, if not the greatest, mathematician of all time. His most important accomplishments were in algebra, geometry, and number theory. Thus, if you have some time at your disposal, you should treat yourself and read about his life story.

Let us get back to the topic at hand. Euler was walking through the city of Königsberg and noticed the \(7\) bridges of the town. Since he went for walks quite often, he wondered whether it would be possible to start his walk at any place in the city and cross every bridge exactly once. It did not matter to him where the end of his walk would be. That route would truly be the most mathematically pleasing route for him to take. In his honor, today we call such routes Euler paths or Euler walks. Instead of trying to explain the layout of the bridges at the time, let us make things clear with a graphic, Figure 1. [1]

A top down view of the seven bridges of Königsberg.
Figure 1. The layout of the bridges that Euler encountered in Königsberg. The blue coloured part of the image is the river Pregel, the black rectangles are the seven bridges of Königsberg, and the lonely figure in blue is Euler wondering what path to take.

Now would be a good time to try and solve the problem for yourself before you read the solution.

Euler, like you, tried some possibilities and came to the conclusion that it was not possible for him to cross every bridge exactly once on his afternoon strolls. The problem quickly piqued his interest. Why was it impossible for him to take a route crossing all the bridges? Was this true for any number of bridges? Did the answer depend on the layout of the bridges?

Just like that, there were more questions than before and he was set on answering all of them. We want to follow in his footsteps and do the same in this article.

Translating problems into graph theory

First of all, it is important to extract the essential information from the graphic. We note that it does not matter which path we take on land. Thus, we only need to focus on the bridges. Let us assign one vertex, or node, to each part of land. If there is a bridge from one landmass to another, we connect the two respective vertices with an edge. Figure 2 shows the map of Königsberg and the vertices and edges mentioned before in one image.

A top down view of the seven bridges of Königsberg. The image also portrays how we can translate the real life problem into a graph theoretic problem by replacing the bridges with edges and the land masses with vertices.
Figure 2.  The map of Königsberg and the corresponding graph are both visible in this image. The image also portrays how we can translate the real life problem into a graph theoretic problem by replacing the bridges with edges and the land masses with vertices.

Now that we know what to focus on, we can simply remove the map from Figure 2 and solely display the graph, as seen in Figure 3.

The image shows what the Königsberg bridge problem looks like when fully translated into a graph theoretic setting.
Figure 3. The image shows the graph representing the seven bridges of Königsberg. The bridges are edges and the landmasses are vertices in this representation.

We have just translated the bridge-crossing problem into a graph-theoretic problem. (Of course, it was a graph-theoretic problem all along, we just had not realized it yet.) We now have all the necessary information to solve the questions in one image, Figure 3 with no unnecessary drawings.

The creation of graph theory

 As mentioned above, we are following Euler’s tracks. Fortunately, Euler’s footsteps led him to his discovery or, depending on your mathematical philosophy, creation of graph theory.  This problem was the first mathematical problem that we would associate with graph theory by today’s standards. Thus, just like in the article From Coastlines To Fractals, an entire mathematical field got created because someone noticed something odd in their daily life.

In order to simplify the paragraphs that follow, we make use of the same definition for the degree of a vertex \(v\) as in the article titled Friendship Paradox. The degree of a vertex \(v\), denoted with \(d(v)\) is the number of edges at \(v\). E.g. the vertex at the top of Figure 3 would have a degree of 3 and the vertex in the middle would have a degree of 5.

Equipped with adequate notation, let us consider a vertex that is not the starting-point or endpoint of a potential Euler walk. It is obvious that we have to arrive at this vertex as often as we leave the vertex. If that were not the case, we would be dealing with the start or end of the Euler walk. Thus, all vertices that are not the starting-point or endpoint of the walk have to have even degree. We distinguish between the two cases for which an Euler walk is possible:

  • The starting-point and endpoint of the walk are one and the same vertex. Then, this vertex would have to be of even degree as well. 
  • We start our walk at a vertex \(a\) and end our walk at a vertex \(b\), where \(a \neq b\). If we ever pass through vertex \(a\) again before reaching \(b\) we obviously must also leave vertex \(a\) again. Thus, the degree of \(a\) has to be odd. Similarly, we are able to prove that \(d(b)\) has to be odd as well.

These are all possible cases for which an Euler walk is possible.

We now solve the bridge-crossing problem as presented in Figure 3. We note that all vertices in the graph have odd degree. Since there are 4 vertices in our graph that have odd degree, there can not be an Euler walk in this graph. Thus, we come to the same conclusion as Euler and can confidently claim that it was not possible to take a stroll through Königsberg and cross every bridge exactly once.

Generalizations

As it turns out, the conditions that we just established are not only necessary but also sufficient for the existence of an Euler path and there is a generalization due to Barnett: [1]

In a graph \(G\) there is an Euler path if and only if there are either  \(0\) or  \(2\) vertices with odd degree.

Since we are following Euler’s footsteps, we are happy with simply mentioning this result here without a proof, just like he did. 

Conclusion

A lot of great ideas or observations were made by innovators letting their thoughts roam freely while roaming freely themselves. Not a lot of people can claim that they were ever involved in the creation of a mathematical field because they took a stroll through town. Fortunately, Euler was one of them and we have the joy of following his thoughts and trails today.


References

[1] Barnett, J. L. (2005) Early Writings on Graph Theory: Euler Circuits and The Königsberg Bridge Problem. Retrieved 20:19, September 16, 2018, from www-users.math.umn.edu/~reiner/Classes/Konigsberg.pdf


Elias Wirth

The Math Section is my personal website dedicated to applications of mathematics in everyday life. The intention behind this project is to make mathematics more approachable to the public while staying mathematically rigorous. I have a Bachelor's degree in Mathematics from the University of Berne and am currently working on my Master's degree in Mathematics at the ETH Zurich.

2 Comments

Priya Asthana · September 22, 2018 at 07:18

Wow, thoroughly loved reading your article. I love telling such math stories to my students . This will be very helpful in taking children on the path of maths discoveries. Keep up the great work!

Elias Wirth · September 22, 2018 at 10:13

Hello Priya

Thank you for the compliment. I am honored that you use my article to get children excited about mathematics. It means a lot to me. Have a nice day and thank you for commenting.

Leave a Reply

0