Puzzles | 'The Seven Bridges of Königsberg' Gets a Facelift

Say hello to Kaliningrad. This Russian city is more famous in the English-speaking world as Königsberg, a major center of East Prussia, birthplace of Immanuel Kant, and setting of “The Seven Bridges of Königsberg,” possibly the most famous logic puzzle in the history of mathematics.

Of Königsberg’s famous seven bridges, five survived bombing during World War II before the city was taken by Soviet forces. In one of those moves that make international dinner parties awkward forever afterwards, the U.S.S.R. held onto the land surrounding the city and turned it into the Kaliningrad Oblast, thus securing a 5,800 square mile enclave sandwiched between Poland and Lithuania.

But several hundred years before that, “The Seven Bridges of Königsberg” was giving mathematicians headaches. The only relief came when German wunderkind Leonhard Euler solved the problem in 1736.

The puzzle goes like this.

The city of Königsberg lies on either side of the Pregel river. Two islands, one large and one small, split the river. Seven bridges connect the mainland to the islands and the islands to each other. It looks like this; or go here for some helpful highlighting.

Now, is it possible to walk through the city crossing every bridge exactly once? You may start and end anywhere you choose. Once you step foot on a bridge you must cross it to its end. You may not reach the islands or the banks by any means other than a bridge. And no you can’t blow anything up.

Give up?

Don’t feel too bad. The guy who finally solved the problem may have more theorems named after him than anyone else. He also managed to convince everyone that the natural constant e raised to the power of the imaginary number i times π is equal to -1. Which is true. But that’s a whole other story. Euler solved “The Seven Bridges of Königsberg” by showing that there is no solution. There is no route through the city that crosses every bridge exactly once.

Here’s how he did it. Euler argued that the relative positions of the landmasses don’t matter. The only thing that matters is how those landmasses — which we’ll also call nodes — are connected to one another. Let’s call the north shore of the river A, the south shore B, the small island H and the big island I.

We know that A is connected to I by two bridges and to H by one. A thus has three bridges in total. B is the same as A. I is connected to H, A and B by one bridge each. H has a total of five bridges: two to A, two to B, and one to I.

Every node has an odd number of bridges. A, B, and I have three and H has five. This is the key to the problem. Every time we enter a node we must also leave that node by another bridge (except at the beginning and the end of our walk). Therefore, the number of times we enter a node must equal the number of times we leave it. And if we cross each bridge only once, then the number of bridges connected to that node must be even (because the number of times we enter and leave a node must be even). This is obviously impossible in the city of Königsberg. Therefore no such path is possible. QED.

Let’s take it more slowly. Euler’s method here is a good example of a proof by contradiction. We assume that a path is possible and then show that a contradiction follows from that assumption. Let’s start on the north bank A and assume that we end on the south bank B. Between the beginning and the end of our walk, we must enter and leave nodes I and H an even number of times. But we already know that I and H have an odd number of bridges, so it is impossible for us to enter and leave either of these nodes and even number of times and cross each bridge exactly once.

No joy, Königsbergers . . . Erm . . . Kaliningraders.