The Bridges of Königsberg
The city of Königsberg was founded in 1255 in Prussia, which was then part of Germany. The city was laid out across a fork in the River Pregel, with seven bridges connecting the different parts of the city.
People who lived in the city often wondered idly over coffee whether it would be possible to make a journey through the city, crossing all of the bridges, but without crossing any of the bridges twice. Each bridge would be crossed exactly once in some direction – such a feat became known as ‘walking the bridges’. People struggled to find a solution to this problem, and it took a mathematician – Leonhard Euler, who lived in nearby St Petersburg – to find the answer.
Euler was a Swiss mathematician, physicist, astronomer, logician and engineer, born in 1707 in Basel, Switzerland. He was well known for making many great and deep contributions to mathematics, and has more published works than any other mathematician ever. He also introduced much mathematical terminology and notation that is still used today.
Among his many contributions was the theory of graphs, which was inspired by his work on the Bridges of Königsberg problem – the paper he published on the problem in 1736 is regarded as the first in the history of graph theory.
Euler was able to answer the question of the Bridges of Königsberg using his new-found theory – by first working out a general rule for all similar problems, then applying this understanding to the specific seven bridges problem. Often in mathematics, generalising a problem to see how it works in different cases can be a great way to get an understanding of the overall problem, and in this case it spawned an entire branch of mathematics.
Graph Theory
Graphs are networks of vertices (points) connected by edges (lines), and can be used to model all kinds of real-world and theoretical problems. The idea of a graph is to show how objects are connected without worrying about actual distances, angles or the geometric shape of the graph. Euler called it the ‘geometry of position’, as position rather than distance had become the significant factor.
You could draw a vertex for each of the numbers 1-10 and connect them with an edge if the numbers share a common factor; you could model the friendships within a group of people using a graph; or you can use them to describe physical networks – graphs are useful in designing, modelling and planning networks such as train lines, utilities supply and delivery routes.
In these kinds of real-world networks, there’s other important information, like the distances between stops, or how long it takes to travel – but you don’t need this information to draw a graph. Many train route maps are drawn using a pure graph, as the actual distances between stations aren’t as important, rather just the connections between the stops.
This difference can be seen in these two copies of the London Tube Map – on the left (image from TFL.gov.uk) the map is laid out to clearly show the connections between the stations, but the positions of the stations are not the same as they are on a real surface map. On the right (image from london-tubemap.com) the positions of the stations and lines are accurate, but this map is less useful to plan a journey – some stations are bunched up close together so it’s harder to make out what’s going on, and there are large gaps between some stations which make the map bigger than it needs to be.
It is possible to store more information in a graph than just the way things are connected – some graphs have arrows connecting the vertices instead of just plain edges, and these are called directed graphs or digraphs – they store information about which way you are allowed to travel along the edge, if this information is important – for example, if the connections you’re modelling are one-way, and a double arrow can be used to indicate a two-way connection. It’s also possible to assign a number (a weight) to each edge, so you could encode distances or travel times, and this is called a weighted graph. The variety of problems that can be modelled using graphs is impressive – and the Bridges of Königsberg problem has the honour of being the first.
Euler Paths
The problem of ‘walking the bridges’ in Königsberg can be seen as equivalent to the following problem: if the city is drawn as a graph with a vertex for each part of the city and edges where the bridges connect the different parts, can we find a path which travels along each edge exactly once?
We define an Euler Path as a route which travels along all the edges of a graph, in some direction, exactly once each edge. It may involve visiting a vertex more than once, as long as that vertex has enough edges connected there. (The problem of traversing a graph and visiting all the vertices once is a separate question.) It’s also possible, for some graphs, to create an Euler Circuit – one which travels along all the edges and finishes at the same vertex it started at.
One property of a graph that’s relevant to this is the number of odd and even vertices in the graph – a vertex is odd or even depending on whether it has an odd or even number of edges meeting there. The number of edges meeting at a vertex is called the degree of the vertex.
If a graph has exactly two odd vertices, it’s possible to find an Euler Path starting at one of these two vertices and finishing at the other. If the graph has no odd vertices at all, it’s possible to create an Euler Circuit, starting and finishing at the same vertex (and this can be completed starting anywhere in the graph).
Euler discovered all of this by sketching Konigsberg, and other graph layouts, and comparing their properties to determine exactly what makes a graph possess an Euler path.
So what does this mean for the city of Königsberg? The four islands (or vertices, in the equivalent graph) all have either 3 or 5 bridges meeting there. This means it’s not possible! If you spent a while trying, don’t feel bad – but Euler’s achievement of proving why it’s not possible is in some sense a solution to the original problem. Quite often in maths, if something can’t be done, it’s still satisfying to fully understand why, and in this case it’s lead to the development of some hugely interesting and useful mathematical ideas.
Today, due to historical restructuring after bombing damage in the war and other building since, two of the original seven bridges are no longer standing, and others have been added – such that it is now possible to cross all the bridges of Königsberg (which is now part of Russia, as of 1945, and is called Kaliningrad) in one Euler path. I guess that’s one way to solve a problem – although it has taken hundreds of years!
A bridge too far
If you’re dissatisfied with an impossible puzzle, here’s a variation on the original. Imagine the city of Konigsberg is inhabited by two rival families – the Red family, occupying the south bank of the river, and the Blue family, who live in the north. Within the city, each family has their own schloß (castle) marked on the map in their own colour, and there’s also a gasthaus (inn) marked in yellow in the centre.
- While everyone in Königsberg knows it’s impossible to ‘walk the bridges’, Baron von Blue comes up with a plan to build an eighth bridge in the city. He wants to position it so that he can leave from his castle on the north bank, walk the bridges, and finish at his favourite gasthaus – but he would like to place it so that it doesn’t enable his rival, Lady Red, to complete the same trick starting from her schloß. Where should the eighth bridge be built?
- Lady Red, on discovering this deception, comes up with her own plan – to build a ninth bridge. It should enable her to walk the bridges, starting from her castle in the south, and finish at the gasthaus for a celebratory round – but it should make it now impossible for Baron Blue to do the same thing from his schloß in the north. Where does the ninth bridge go?
-
After seeing these two rivals wreak havoc on the city with their inane bridge building (and quite dismayed at the amount of time people are spending at the gasthaus), the Bishop decides to scupper all their plans by building a tenth bridge. He’d like to make it possible for anyone who lives anywhere in the city to walk the bridges, and return home to their own homes. Where should he build a tenth bridge?
Katie Steckles wrote (29. May 2018):
> […] here’s a variation on the original [problem. …]
> Where should the eighth bridge be built? […]
Any answer to the question “Where ?” should presumably be given in terms of a pair of nodes which are individually identified (labeled, or coloured); referring to the three colours (“blue”, “red”, “yellow”) mentioned in the problem statement, and an additional fourth colour (e.g. “white”) for naming the node (a.k.a. Lomse) with (originally, only) one edge/bridge to each of the other three nodes.
p.s.
SciLogs-Kommentar-HTML-Test:
“K<sub>4</sub>” wird dargestellt als: “K4”.
Or you can just draw it on the diagram! 🙂
Katie Steckles wrote (30. May 2018 @ 12:03):
> Or you can just draw it on the diagram! 😉
Your smiley is adding insult to injury, because for us humble SciLogs-commentators there are not even the HTML-“<pre> … </pre>” tags made available, to draw consistently formatted ASCII pictures.
On a precious few pages we might at least get \(\LaTeX\) turned on …
“The city of Königsberg was founded in 1255 in Prussia, which was then part of Germany.”
Small correction: Prussia did not belonged to Germany in this time, it belonged to the State of the Teutonic Order, but this State was not part of the Holy Roman Empire. Prussia became part of Germany only in 1871.
Thank you, great fun to read this article.
Wondering about Mr. Euler’s approach, I like the idea that he came from St. Petersburg to study the problem personally by walking around in Königsberg. This should have happened somewhat around 1735.
I suspect that he was able to spot a good cafe there for putting down his notes, before he had to get back onto the coach for travelling home to “nearby” St. Petersburg. “Nearby” stands for about 825 km direct distance. Depending on the quality of the road at that time a coach could reach a speed of 2km/h up to 10 km/h – plenty of time for Mr. Euler to deal with the “Königsberger Brückenproblem”. I have no idea how – at that time – a sufficient coffee supply for travelling scientists could have been established aside the road in between the two cities.