The city of Königsberg, now Kaliningrad, is located on the two shores of the Pregel River. In the early 1700s seven bridges connected two islands on the river to each other and to the mainland. Residents often discussed if it was possible to traverse the city, crossing all the bridges once and only once. The starting and ending points of the walk need not be the same. People struggled to solve the problem until Swiss mathematician Leonhard Euler came along.
Euler made immense contributions to physics, astronomy, logic, engineering and especially mathematics. He has more published works than any mathematician to date. Among his works was a paper published in 1736 discussing the Seven Bridges of Königsberg.
“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.”- Leonhard Euler, March 1736
By generalising the problem, Euler opened up an entirely new branch of mathematics- graph theory. Euler’s relevation? Don’t just look at the bridges, look at the landmasses too!
Graphs
Graphs are networks of vertices (points) connected by edges (lines). They are used to model many real-world and theoretical problems, including optimizing train routes and delivery routes, drawing molecular maps, and even mapping your network of friends on Snapchat. The purpose of a graph is to show how objects are connected. Distances, angles or the shapes of graphs are irrelevant.
We can visualize the city of Königsberg as a graph with four vertices (the different regions of the city) and seven edges (the bridges connecting the regions). An equivalent formulation of the Königsberg problem is now the following: Is possible to traverse the Königsberg graph such that that each edge is crossed exactly once?
Euler Paths and Euler Circuits
An Euler Path is a route which travels along each edge of a graph exactly once. A vertex may be traversed multiple times, provided it is connected to sufficient edges. For this problem, the starting and ending vertices need not be the same. However, there exist graphs termed Euler Circuits which contain routes that travel along all the edges of the graph and finish at the same vertex they started at.
The degree of a vertex is the number of edges connected to it. In this case, the degree of a region is the number of bridges that go to connect to it. An odd vertex is a vertex whose degree is odd. An even vertex is a vertex whose degree is even.
Notice how it’s not possible to construct a graph with an odd number of odd vertices. Since each edge connects two vertices, the total degree of a graph is always twice the number of edges it has. So the total degree of a graph is always even. A graph with an odd number of odd vertices, say 3 odd vertices of degrees 3, 5 and 7, will result in a graph that has a degree of 3 + 5+ 7+ 2x = 5 + 2x (x=number of edges connected to even vertices). This produces an odd total degree of the graph, which is impossible.
Observe the following graphs. Can you find Eulerian paths or cycles for any of these graphs?
Taking a closer look,
We obtain the following table:
On experimentation you may find that these observations hold good for any graphs that contain Eulerian circuits or paths.
Notice how all the vertices of cyclic graphs are even. Similarly no graph with an Eulerian path has more than two odd vertices.
And wait, there’s more. We’ve established that no graph can have an odd number of odd vertices. So no graph can have just one odd vertex. If a graph that has an Eulerian path has zero odd vertices, all its vertices are even and it is also a cyclic graph. This type of graph is termed an Eulerian graph. For a graph to have an Eulerian path but not an Eulerian cycle it must therefore have two and only two odd vertices. This graph is semi-Eulerian.
Back to the Königsberg dilemma. The Königsberg graph has four odd vertices. There is no Eulerian path on this graph. Euler’s "geometry of position” decreed, much to the disappointment of residents, that one could not traverse Königsberg and cross each bridge only once. Such a walk did not exist.
Problems
Imagine two rival queens live in palaces on either bank of the Pregel River: the Green Queen, who lives in the south bank, and the Purple Queen, who lives in the north. Königsberg's finest restaurant, Adelinas Ballhaus, a favourite of both queens, is at the center.
Fascinated by graph theory, the Purple Queen asks her courtiers to build an eighth bridge. This bridge must positioned such that she may leave from her palace, walk all the bridges and finish at Adelinas Ballhaus. However, she does not want the Green Queen to be able to do the same starting from her palace. Where should the courtiers position this eighth bridge?
The Green Queen’s faithful spies inform her of the Purple Queen’s plans. The Green Queen, although displeased with the quality of Königsberger klopse (meatballs) at Adelinas Ballhaus as of late, is spiteful, and decides to build a ninth bridge. This bridge must allow her to start from her palace, walk the bridges and finish at Adelinas Ballhaus whilst making it impossible for the Purple Queen to do the same. Where should she position the ninth bridge?
Furious at the endless construction and discord raging through the city, the Mayor of Königsberg decides to put a stop to the Queens’ games. He orders the City Council to build a tenth bridge. This bridge must allow any resident of the four districts of Königsberg to walk the bridges and return home. Where should they build a tenth bridge?
Aftermath
In 1875, the residents of Königsberg, perhaps with the intention of solving the Konigsberg problem once and for all, constructed a new bridge between the center and the south bank. This meant that these two landmasses were connected with four bridges each. Only two vertices had an odd number of edges, meaning that the walk was now possible.
The future of Königsberg was grim. During WWII British bombers destroyed both the old town and the northern parts of Königsberg. Russian forces occupied Königsberg in 1945, forcing German civilians to risk their lives and evacuate the town by boat in the midst of the cruel January winter. In the span of just a few months, the Red Army managed to capture Königsberg, with most of the old city in ruins.
Renamed Kaliningrad, the city looks much different now. The bombings destroyed many of the bridges, and it is not possible to pose such a problem now. Despite the city’s grim fate, the residents’ old coffeehouse conversations of “walking the bridges” created a branch of mathematics of utmost importance- graph theory. And the city itself? Well, it has maintained its coffeehouse charm!
References
If you liked this article, let me know using the contact forms below! Please feel free to email me at arushee.tj@gmail.com with any questions, problems, solutions or suggestions for future blog posts. Until next time :D
Comments