📂Graph Theory

The Solution to the Bridges of Königsberg Problem

Problem ¹

The Seven Bridges of Königsberg is a problem about whether it is possible to traverse each of the city’s seven bridges exactly once and return to the starting point. At first glance, without knowing the solution, it seems like a daunting problem that requires checking every possible route. It doesn’t obviously appear to be a mathematical problem, and though it feels like it might be solvable by exhaustively checking all cases, that approach is not as easy as it sounds.

The great mathematician Euler ingeniously turned it into a graph problem and solved it beautifully. The astonishing part is that he solved it at a time when graph theory was not even a focus of academic attention, let alone considering spaces topologically. Essentially, Euler brought future concepts to solve a problem with a future methodology. Let’s take a closer look at what his solution was.

Solution

The image above can be simplified as follows:

If we consider the regions divided by the river as vertices and the bridges connecting the regions as edges, we get the following graph:

Now, the problem of the Seven Bridges of Königsberg has transformed into a graph problem where we must determine if there is a closed trail (method) that includes all edges (crosses all bridges) and returns to the start. Such a graph, which contains a closed trail involving all edges, is referred to as an Eulerian graph.

Euler’s theorem: Let $G$ be a connected graph. $G$ being an Eulerian graph is equivalent to all vertices in $G$ having even degrees.

According to the criteria for an Eulerian graph, if there is even one vertex with an odd degree, then it is not an Eulerian graph. The graph above has vertices with odd degrees only, so it is not an Eulerian graph. This implies that there is no way to traverse all bridges of Königsberg and return to the starting point.

■