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 18^th century mathematicians, Leonhard Euler.

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.