Seven Bridges

Suppose that you live in a town that sprawls across the banks of a branching river, with an island in the middle. Seven bridges link the different parts of town. One sunny summer day, you decide to take a bike ride. Looking at a map, you try to find a route that would take you across all the bridges and back to where you started. You also add the challenge never to cross the same bridge more than once. If you succeed, you decide, an ice cream reward awaits you on your return.

Is it possible to find such a route? Try it.


This illustration shows the seven bridges (green) of 18th-century Königsberg.

It turns out there is no such route. The first person to prove that it can't be done, nearly 300 years ago, was a famous mathematician named Leonhard Euler (pronounced OIL-er). The puzzle originally concerned a city in northern Europe, Königsberg, which really did have a branching river running through it, with an island and seven bridges. (The city is now called Kaliningrad and is part of Russia.)

In essence, the bridges connect four separate pieces of land. Anyone standing on any given land mass would have to have a way to get on and, if they wanted not to cross the same bridge twice, a different way off. That means each land mass would require an even number of bridges. However, in Königsberg, each land mass has an odd number of bridges. As a result, all seven bridges can't be crossed without crossing one of them more than once.

Leonhard Euler was an amazing person. Some people describe him as the greatest mathematician of all time. He was born in Basel, Switzerland, on April 15, 1707 (so this year was the 300th anniversary of his birth). As a young boy, he found it very easy to learn languages. He had an extraordinary memory and could do all sorts of mental arithmetic with astonishing speed. He entered the University of Basel at the age of 14 and obtained his degree three years later.

Interestingly, if you were to visit Kaliningrad today, you would find that two of the bridges no longer exist, and a single bridge has replaced a pair of the bridges that crossed from one side of the river to the other via the island. A set of stairs in the middle of the bridge allows you to visit or leave the island.


This satellite image shows Kaliningrad today, with its new arrangement of bridges.

It's now possible, if you start on the island, to follow a route that crosses all the bridges without crossing any one of them twice. With this restructuring, the city planners may have thought they were foiling Euler's toiling. But of course, being a mathematician, Euler didn't just solve a single problem—he solved the problem generally. That is, he worked out rules for figuring out whether such routes exist for any number of land masses and bridges.

---

Muse, July/August, 2007.