The 7/5 Bridges of Königsberg/Kaliningrad

Then...
seven bridges of Königsberg (Koenigsberg)

In the 18th century Euler proved that it was not possible to plan a route that would cross each of the seven bridges of Königsberg exactly once, whether or not you ended up in the same place as you began.

For more information on this problem and its generalization, do an internet search on Euler, bridges, and Königsberg, or look in a book about graph theory.

woodcut of Euler's profile, looking somber woodcut of old Koenigsberg abstract rendering of the seven bridges: two edges AB, two AC,
      one each AD, BD, and CD

Now...
five bridges of Kaliningrad

All seven bridges were destroyed by an Allied bombing raid in 1944 and only five were rebuilt. Königsberg, along with the rest of northern East Prussia, became part of the Soviet Union (now Russia) at the end of World War II and was renamed Kaliningrad. Now it is possible to visit the five rebuilt bridges via an Euler path (route that begins and ends in different places), but there is still no Euler tour (begin and end at the same place).

collage consisting of: map of downtown Kaliningrad, abstract seven
bridges with two crossed out (the new graph has no parallel edges, only one
each of AB and AC), pictures
of smiling Matt Stallmann on each of the remaining five bridges)

Practical applications of this particular "solution" are limited. To follow the planned route, you have to start on one island in the river Pregel and end on the other.
Helicopter drop off and pickup can be arranged for a price.
A far more interesting challenge is getting to Kaliningrad in the first place. See if you can do it within 24 hours, starting without a Russian visa. That's likely to be the lower bound. The current upper bound is 2-3 weeks, including a 16-hour train ride from Berlin.

True confession:

The real reason for the Kaliningrad trip was that my father spent the first 20+ years of his life there and its surroundings (now called the Kaliningrad Oblast). My grandfather designed a railway station in Kaliningrad, the cascades of the Schlossteich (castle pond or lake), and a beach house on the Baltic in Rauschen, now Svetlogorsk. All of these are still standing and being used, although the "being used" part is debatable with respect to the cascades.

My brother Cornelius and I had to visit the bridges -- or our graph theory/topology/discrete math colleagues would have never let us hear the end of it if we didn't. We cheated, of course, and only went halfway across and back for two of the bridges. But two half bridges = (get your paper and pencil).

Meanwhile, my parents and a close friend whose father also grew up in Königsberg enjoyed coffee and dessert at an upscale cafe near bridge number 2. I still occasionally look at the cafe's souvenir menu with its full color pictures of all the offerings and ponder what might have been... Time to move on, and this web page is a major step.

You didn't think I was that much of a math geek, did you?

Here I am trying to explain to my friend Eric what all the fuss is about. My mother is, understandably, amused.

Eric and I facing each other (I'm writing on a pad of paper); my mother and father are looking on


Photos by Cornelius Stallmann

Matthias F. (Matt) Stallmann, http://people.engr.ncsu.edu/mfms (Matt UNDERSCORE Stallmann AT ncsu DOT edu

(Konigsberg) Modified: Tue 2009-06-02 22:07