Some of my students gave a presentation today on graph theory, and talked about the Bridges of Königsberg. Königsberg was founded in 1254 and is part of the Russian enclave Kaliningrad. And it shows up in math talks because of its bridges. As a brief background, the Pregal River runs through the city and splits in two; there’s also an island, so there are four different land masses. You can kind of see this in the following map from 1652 (which appears in almost any math talk on the subject):

But it’s hard to see the river there, so some nice person colored it in in the map below. And they also colored in the seven bridges connecting the island and the different banks:

The quickie version of the story is that people wondered if it was possible to walk across all the bridges exactly once while on a Sunday stroll, but no one could figure out how, and they called Leonhard Euler (who Wikipedia says is actually Leonhard Paul Euler, but, well, as much as I love Wiki I’m just not sure I believe that) in to solve the problem and he invented graph theory and said No. OK, he didn’t actually draw a picture of a graph — my non-Wiki source tells me that first appeared in print about 150 years later, around 1890 — and instead he used a combinatorial argument. But the end result was that No, you can’t cross all the bridges exactly once. You’ll have to skip one and save it for next week, or cross one more than once.

And the reason boils down to the fact that all four land masses have an odd number of bridges (the north shore, south shore, and east bank each have 3, while the island has 5). If they’d all had an even number of bridges then it’d be possible and you’d end up where you started, and even if just two of them had an odd number of bridges you’d be OK if you were willing to start at one of those odd-bridge land masses (you’d end up at the other, and have to repeat a bridge crossing to get back to your car). But with all odd numbers of bridges it’s impossible.

The presentation explained all this, and then one of the speakers mentioned that two of the bridges were destroyed in World War II, and two more destroyed later by the Russians, and more were built, and now after all this time, it’s possible. And I thought to myself, “I wish I could go see Königsberg.” And then I thought GOOGLE MAPS! because lately I’ve been having way too much fun looking up stuff on those satellite photos, even if it sometimes takes ages to load. So I checked it out and sure enough, you can see the bridges today!

Look! There it is! With the zoomed out version you can see 4 bridges on the north shore, 3 on the south, 4 on the east bank, and 3 on the island, so it looks like it’s possible to walk along all the bridges at once after all, as long as you don’t mind ending up in a different place from where you started. And as long as you don’t mind walking along what looks to be a major highway. But still, I’m sure the people of the 1730s would be happy to learn that their Sunday stroll problem has finally been fixed.

Tags: bridge, Euler, graph theory, konigsberg

December 29, 2008 at 5:42 pm |

[…] on the subject and so have seen an old map of Königsberg several times. Using googlemaps, the guys over at 360 showed that if we pose the Königsberg problem today then the result is completely […]

May 1, 2009 at 9:59 am |

The amazing internet! I’m planning to play with this problem with some students today and my math salon tomorrow, and just stumbled across this post while perusing your blog. What serendipity!

I heard a lovely talk back in the 80’s, given by a man named John H. Hodges, titled 5 Major Steps in Mathematical Creation, which used this problem as its exemplar. I’d love to contact him to ask if I can post the notes he gave at that talk (on ditto!), but I haven’t managed that yet.

Thanks for some great material.