Some time ago, I wrote this article about how the mathematician Leonhard Euler laid the first foundations of graph theory in his famous problem of the seven bridges of Königsberg, nowadays Kaliningrad. The puzzle, which fascinated the city’s inhabitants, was stated as follows: Can you walk through each part of the city, while crossing each bridge exactly once and without retracing your steps? Such a walk is nowadays also known as an Eulerian path. Euler approached this question in a way radically new for his time. Instead of focusing on exact geographical details, like distances, he focused only on connections between different parts of town. In his abstracted representation, each of the four landmasses became a point and each bridge a line connecting two points. In doing so, Euler transformed a real-world walking problem into an abstract mathematical structure, which we nowadays call a graph. Using simple logical reasoning, he could then prove that a walk fulfilling the constraints of the puzzle was impossible, i.e., it is impossible to find a route that crosses all seven bridges exactly once. (Can you argue why that is the case? If not, have a look at the previous article!)
I concluded my previous article with a challenge: Knowing that modern-day Kaliningrad has a different bridge layout, does Euler’s impossibility-conclusion still hold today, or has the puzzle become solvable? In this article, let us use graph theory arguments to find out together.
To solve the modern day version of the Kaliningrad bridge problem, we shall proceed in the same manner as Euler, by abstracting the situation and ignoring unnecessary details. The exact path one takes across any neighbourhood does not matter. What matters is only how the landmasses are connected to one another through the bridges. As in our last article, we can label the four regions Kneiphof, Vorstadt, Altstadt, and Lomse simply as A, B, C, and D. The five still remaining bridges, labelled a, b, c, d, e, connect these regions.
We can then simplify things even further by replacing each region in Figure 2 by a node and each bridge by a link connecting two nodes. The resulting structure is a graph, in which unessential geographical details are obscured, leaving only information about connectivity.
Now the initial question becomes surprisingly simple: Can we draw this graph in one continuous stroke, without lifting the pen or retracing a line? In mathematical terms, we are asking whether the graph contains any Eulerian paths. Euler discovered a beautifully simple rule: an Eulerian path exists only if at most two nodes have an odd number of connections (also known as an “odd degree” of the node). As a fun exercise, you may try to convince yourself that there can never be only one node of odd degree – more generally, if these nodes exist, there is always an even number of them. If a graph has two odd degree nodes, they must be the start and end points of the walk. In the graph describing the original Königsberg problem, all four nodes had an odd degree. Therefore, achieving an Eulerian walk through the city was impossible.
The modern situation is significantly different: in today’s graph, nodes B and C have an even degree, while A and D have an odd degree. Thus, we can see that Euler’s condition is now satisfied! So the answer to our puzzle is that the updated Kaliningrad bridge problem does have a solution, and we know that any valid walk must start at A or D and end at the other. For example, the walks A–C–D–A–B–D or D–A–B–D–C–A are Eulerian paths.
At first glance these two routes look different, but mathematically they share the same underlying structure. Stretching or bending the drawing without breaking connections does not change the walk itself. This idea leads us directly into another fascinating field of mathematics: topology. Topology studies properties of shapes and structures that remain unchanged under smooth deformations. Typical topological questions include: Is an object in one piece? Can you draw a path from one point to another without lifting your pencil? Are two paths or objects essentially the same? It is important to note that distances, angles, and precise geometric shapes do not matter, only how spatial regions are connected. From this point of view, the historical Königsberg bridge-network and modern Kaliningrad one are fundamentally different. Their connectivity, i.e. the topology, changed and that determines whether the bridge walk is possible or not.
Once you know of topology, you will be able to see it in action everywhere in your daily life. This certainly holds true for the British mathematician and Nobel laureate Roger Penrose, who has described how these ideas occur to him during ordinary walks, in this video.
When going on his strolls, Penrose likes every walk to be different from previous ones. However, by different, he does not just mean slightly varied but topologically different. His method for assessing whether two walks are different or the same goes as follows: imagine walking while dragging an infinitely long piece of string behind you. Two walks count as the same if one string can be smoothly deformed into the other without cutting it or passing through obstacles.This means that small detours do not matter while, for example, walking around a tree changes the topology. If you circle a tree clockwise one day and counterclockwise the next, the string winds differently around the trunk. Because the string cannot pass through the tree, the two paths can no longer be deformed into one another. The tree thus acts as a topological obstacle which can force the walker to take different paths around it. Mathematically, these alternative walks now belong to different topological classes.
Now imagine Penrose encountering not only one but ten trees during a walk. For each tree, he may pass either on the left or the right. Each choice will change the way in which the string winds around the obstacles. In total, one could thus find 2^10, that is more than a thousand, topologically distinct routes. Retracing your steps home, however, adds nothing new and interesting. Topologically, this is known as a null walk since the string simply pulls back along itself.
According to Penrose, it can even be interesting to observe how landscapes evolve over time and thus engender topology-changes in his walks. For instance, a small sapling that you can step over today may grow into a large tree eventually. In this way, time will be turning a trivial bump into a genuine topological obstacle. As new obstacles create new classes of walks, nature has its way of ensuring that even familiar surroundings can become mathematically new again. As Penrose himself remarks, such questions keep him engaged and are “vaguely entertaining in an irritating way” during his everyday strolls.