The Bridges of Königsberg
How Euler developed Graph Theory and gave programmers a whole new way to approach problems
“By and large it is uniformly true in mathematics that there is a time lapse between a mathematical discovery and the moment when it is useful.” — John von Neumann (1903–1957)
The duration between a mathematician coming up with an idea and someone subsequently finding a use for that idea can be a long one. We can see this especially when we look at something like computer science, a subject that is an application of mathematics. For example, Bertrand Russell was a very old man before his Type Theory — which he had developed in his thirties — was put to use in designing programming languages. It was almost a century before George Boole’s ideas of logic were applied to digital electronics.
But for an example of a really long lapse we can take Graph Theory, something that is fundamental to computer science but was first dreamed up two hundred years before the formal existence of that subject. To see this example of embryonic computer science in action we’ll have to travel back to eighteenth-century Prussia.
The Pregolya River runs through the centre of Kalingrad, creating not only a northern and southern side, but also two large islands within it. In the eighteenth century, this city was Prussian and named Königsberg. In those days, there were seven bridges between the four land masses. So beautiful were they, inhabitants enjoyed strolling the city every Sunday, making sure they walked over every bridge. As they did so, it was a popular game to try and figure out a route, such that they could walk over every single bridge, but only once each.
However long this tradition had been going on, by the 1730s no-one had yet been able to figure out such a route. It was probably tempting to claim that it was impossible after all these years of trying, but how could they prove that? An intuitive feeling or suspicion, no matter how strong, is not proof. After all, there’s lots of permutations; it could be that they just hadn’t found the right one yet.
The problem seemed important enough to the Mayor of Königsberg for him to prevail on local genius Leonhard Euler to put everyone out of their misery. Euler was a prolific mathematician and busy man, but what else can you do if the mayor calls on you for help? No doubt with a sigh, he put his manuscripts aside and sat down to solve the trivial little game. Lucky for us that he did, because in the process of solving the conundrum, he laid the foundations for one of the most important concepts in computer science: graph theory.
That map of Königsberg looks pretty cluttered and distracting, doesn’t it? To help us concentrate on the problem at hand, we could just erase all those streets and buildings or, even simpler, just redraw the map without them. In fact, when you think about it, most of the map’s detail is unimportant to the essence of the problem. The size of the land masses is irrelevant, as is their position and distance from each other — all we care about is how each land mass is connected to the other. To really simplify it, we could just represent each piece of land as a circle and each bridge as a line between them. The makers of maps for metros do something very similar, removing all irrelevant details (like distances, absolute positions) and leaving only the useful information, a process called abstraction.
The image above shows our simplified abstract map. That’s better. Everything relevant to the essence of the problem is now visible in the diagram. What you’re looking at is a graph, a scheme which models information using nodes (the circles) and edges (lines connecting the nodes) to represent things and how they relate. On our map, each node represents one of the land masses and each edge corresponds to a bridge connecting two land masses. Now he had his graph, how would Euler solve the problem?
He didn’t want to just try every possible solution — who knows how long that would have taken — but he was sure there was a more methodical approach to the problem. Euler knew, like all computer scientists today, that looking for patterns in problems should always be the first step to seeking a solution, because not only does it make the original problem easier to solve, but it helps to make the eventual solution general and therefore applicable to other similar problems. After all, what if this started a trend, prompting every mayor in Prussia to come banging on Euler’s door with a map of their own city begging to know how best to traverse their city’s bridges? Better by far to just give them some instructions for finding it out themselves.
Euler knew, like all computer scientists today, that looking for patterns in problems should always be the first step to seeking a solution.
Euler noticed a critical feature of the problem. In the original problem, each bridge could only be crossed once. On the graph, this means that each node has to have an even number of connections, because you must enter and leave a node via different edges. The only exceptions are the start and end nodes, because you don’t have to enter the start node via an edge and you don’t have to leave the end node either. Therefore, in order to satisfy the requirements of the walk, all of the nodes in the graph must be connected to an even number of edges; if there are any nodes with an odd number, we can only allow two of them so they may serve as the beginning and ending of the journey.
This explanation demonstrates the power of graph theory. Go back to the previous paragraph and replace every instance of “node” with “land mass”, every instance of “edge” with “bridge” and every instance of “graph” with “city”. You will have transformed the solution back into language that anyone in eighteenth century Königsberg could understand. And yet, the paragraph as written is very general. Not only could it apply to any city and its bridges, but it could also apply to any other problem with similar requirements. Perhaps a tour guide who wants to avoid going multiple times via the same point, or a soldier who wants to mine a group of bridges but not risk going back over the explosives already set.
We can easily convince ourselves that it’s impossible to traverse the bridges of Königsberg as desired, because all land masses are connected via an odd number of bridges. This news, an indisputable proof that their game had no solution, probably disappointed the citizens of Königsberg. When two of the bridges were later destroyed during World War Two, doubtless the citizens were greatly angered. They could at least console themselves that they were left with exactly two land masses connected to an odd number of bridges, thus allowing them to roam their city in exactly the fashion they had wanted to all those years before.
The applicability of graph theory turns out to be truly astonishing. It has been made richer and more expressive over time, with additions being made as required. For instance, graphs now typically include direction (one-way edges) and weight (assigning values to edges that could denote, for example, distance). Today, graph theory is used throughout computing — with applications as diverse as networks, map software and artificial intelligence — as well as mathematics, all the natural sciences, linguistics, and sociology. Any time you need to reason about objects and their relations to each other, be it cities in a sat-nav system or the billions of pages on the Internet, graph theory is the tool you need.
