The Seven Bridges of Königsberg

June 13, 2023

Share this article:

[supsystic-social-sharing id='1']

Written by

Imagine you are taking a stroll around the 18th century Prussian city of Königsberg (currently Kaliningrad, Russia). The river Pregel runs through Königsberg and there are two large islands in this river. The islands are connected to each other and to the mainland by seven bridges. You intend your walk to pass along all seven bridges, and furthermore, that every bridge is crossed once and only once. How?

The problem

First, let us formalise the problem a little more. ­It is not allowed to cross the river in any other way than by utilizing one of the bridges, and one cannot end the path on a bridge. If you tried to find a path complying to these conditions, you will have noticed that it is quite hard to find a proper path. Very hard. In fact, it is impossible. This was proven in 1736 by, whom we may call the Messi of the 18th century mathematicians, Leonhard Euler.


The Problem of the Seven Bridges of Königsberg
By Bogdan Giuşcă – Public domain (PD),based on the image, CC BY-SA 3.0, https://commons.wikimedia.org/w/index.php?curid=112920

Euler’s solution

Euler first noted that for the solution of the problem, the route on the land or bridges itself, is irrelevant. Thus, he rewrote the problem to the abstract mathematical basis, where the only matters of concern are the specific connections between the land masses and the bridges. This way, the problem simplified to the image below, with the two middle green dots representing the two islands and the top and bottom dots representing the mainland. The lines between these dots are the connections between these areas of land, the bridges.

Secondly, Euler observed that for all land masses except for the ones where the path begins and ends, whenever one enters the land mass via a bridge, it must also be exited via a bridge. This means that for all ‘non-endpoint land masses’ we must have that they have an even number of bridges attached to them. In our problem, we have 4 land masses which means that if 2 of these can serve as endpoints of the path, we can have at most 2 land masses which have an uneven number of bridges connected to them, to be able to walk the path. However, all four land masses have got an uneven number of bridges connected to them (5, 3, 3, 3). Following this, Euler concluded that it was infeasible to devise a path which crosses every bridge once.

Influence on mathematics

Euler’s solution is considered to be the first theorem of graph theory and the first true proof in network theory. His rigid simplification of the problem until only the mathematical essentials remain, lays the foundation of graph theory and is viewed as a precursor to the study of topology.

In graph theory the dot replacement of a bridge is called ‘vertex’. The connections between the vertices (the bridges) are known as ‘edges’. Furthermore, the number of edges attached to a vertex is defined as the ‘degree’ of a vertex. The mathematical framework obtained by rewriting a problem into a system of only vertices and edges is called a ‘graph’.

Philosophers note that with his proof, Euler enters a different area of mathematics in which not measurements and calculations are the central theme, but something more general. This cast doubt upon the Aristotelian view that mathematics is the ‘science of quantity’. It must be noted that Euler’s method of simplifying the problem does not lead to an approximation or a model of reality, but merely to a more abstract problem, the solution of which is entirely applicable to reality.

Euler path & Euler tour

The general objective of the Königsberg bridges was later defined as an Euler path, named after Euler. That is – in our new vocabulary – a path through a graph, whereby every edge is crossed once and only once. So, for an Euler path the necessary condition are that the graph must have exactly zero or two vertices which have an odd degree and it must be connected (i.e., there exists a path between any two vertices in the graph). These were later proved to also be sufficient conditions. When an Euler path needs to begin and end at the same vertex, it is called an Euler Tour. For an Euler Tour, every vertex in the graph must have an even number of edges connected to it. In other words, an even degree.

Current situation

During the second world war, Königsberg was bombed by the Allies, and two of the bridges were destroyed. Furthermore, two bridges were replaced by a modern highway and one bridge was rebuilt. Two last from Euler’s time still. This means that 5 of the 7 bridges remain, where in graph theory language, the degrees of the vertices are 2, 2, 3, 3. Therefore, in current times, an Euler path can be found and the Königsberg problem yields a solution. An Euler tour is still impossible.  

Read more

Regression analysis: A beginner’s guide

Regression analysis: A beginner’s guide

Econome­­trics, the int­­ersection of economics and statistics, employs sophisticated methods to analyse and quantify relationships within economic systems. One of its fundamental tools is regression analysis, a statistical technique that allows economists tot model...

Are you tying your shoelaces wrong?

Are you tying your shoelaces wrong?

We tie our shoelaces to ensure that our shoes stay on tight, and we do these by tying a knot. There are different ways to tie your shoelaces, you may have learnt the “around the tree” technique, but somehow, they still always come undone, why? This all has to do with...