Whether it’s timing yourself to see how fast you can fill the coffee maker or counting how many steps it is to the bus stop in the morning, there’s something about the monotony of a daily routine that makes you want to turn it into a game. The people of 18th-century Königsberg, Prussia (now Kaliningrad, Russia) were no different — it’s just that the game they played with the seven bridges in their town ended up sparking the interest of one of history’s greatest mathematicians.
Take Me to the River
Königsberg was built on the banks of the Pregel River, which sliced the town into four separate landmasses that the residents accessed via seven different bridges. According to legend, a popular pastime during Sunday afternoon strolls would be to see if you could cross each bridge exactly once to get through the town. Nobody quite figured out a way to do it, but that didn’t mean it was impossible. They just had to get the right expert to figure it out.
In 1735, Carl Leonhard Gottlieb Ehler, the mayor of Danzig (a city 80 miles west of Königsberg), reached out to Leonard Euler for help with the problem on behalf of a local mathematics professor named Heinrich Kühn. Even then, Euler was a famed and prolific mathematician — he published his first bookon mathematics a year into this correspondence, and would go on to publish more than 500 books and papers over his lifetime.
So it’s no wonder that at first, he thought the problem was beneath him, writing, “… Thus you see, most noble Sir, this type of solution bears little relationship to mathematics, and I do not understand why you expect a mathematician to produce it, rather than anyone else, for the solution is based on reason alone, and its discovery does not depend on any mathematical principle.”
Eventually, however, Ehler and Kühn made Euler realize that this was a whole new type of mathematics: the “geometry of position,” what today is known as topology. In topology, the exact shape or layout doesn’t matter — an old joke is that a topologist can’t tell the difference between a donut and a coffee cup because both have exactly one hole. This brand-new field had so far only been written about; no one had figured out a problem that applied yet. The seven bridges of Königsberg were a perfect proof of concept since it didn’t require any measurements or precise calculations. You could turn the complex map of the town into a clean and simple diagram without losing any information.
A Bridge Too Far
While you might be tempted to solve this problem by mapping out all possible routes through the city, Euler recognized that this strategy would take way too long and wouldn’t extend to any other bridge problems (what if another city had 12 bridges?). Instead, he ignored the bridges for a moment and just labeled the landmasses with the letters A, B, C, and D. That way, he could represent a bridge journey from A to B as AB, and a journey from A to B to D as ABD, for example. (In Euler’s approach, which bridge a person uses doesn’t matter.) It’s essential to note that the number of letters in a journey is one more than the number of bridges crossed: an AB journey crosses one bridge, an ABD journey crosses two, and so on. Euler realized that because Königsberg has seven bridges and you need eight letters for a seven-bridge journey, the solution to the problem would require eight letters.
Next, he came up with a more general rule using an even more simplified diagram. If you had just two landmasses, A and B, and you crossed bridge a once, then A would be either where the journey began or ended — but you’d set foot on A exactly once. If you crossed bridges a, b, and c one time apiece, then you’d set foot on A exactly twice. That led to a handy rule: If you have an odd number of bridges to a landmass, you can add one to that number and divide by two to get the number of times that landmass needs to be used in the journey. (In this example, adding one to the three bridges gets you four, divided by two gets you two, which is how many times you use landmass A).
That brought Euler back to the original problem. There are five bridges that lead to A, so it needs to be used three times in the eight-letter solution he’s looking for. B, C, and D all have two bridges that lead to them, so they each need to appear twice. But 3 + 2 + 2 + 2 is 9, not 8, even though you must land on only eight landmasses for seven bridges. That means that you can’t travel through the town of Königsberg by using each bridge exactly once — it’s impossible.
Like any mathematician worth his salt, however, Euler didn’t stop there. He went on to make a more general rule for other towns with other numbers of bridges. If a town has an odd number of bridges, then there’s an easy way to figure out whether you can make the journey or not: If the sum of the number of times each letter must appear is one more than the number of bridges (like the eight-letter solution we noted in the first paragraph of this section), you can make the journey. If the sum is greater than that, then you can’t.
But what about even numbers of bridges? In that case, it depends on where you start. If you start in landmass A and travel over two bridges, A would appear twice in your solution. If you start on the other side, then A would only appear once. If there are four bridges, then A appears three times if it’s a starting point and two times if it’s not. That means, as a general rule, that if the journey doesn’t start in A, it should appear at half the frequency as the number of bridges (4 bridges divided by 2 equals 2 times). If the journey does start in A, then it should appear at half the frequency plus one (4 bridges divided by 2 plus 1 equals 3 times).
The brilliance of Euler’s solution isn’t in the answer, but in the method he used to get there. This was one of the first examples of graph theory, also known as network theory — an essential area of mathematics in today’s world of transportation networks, social networks, and electronic networks. As for Königsberg, the town eventually added another bridge, making Euler’s solution moot — and that was before British forces destroyed much of the town during World War II. Today, both the town and the river have new names (Kaliningrad, Russia, and Pregoya), but that old problem lives on in a whole new branch of mathematics.