The Seven Bridges of Königsberg

In the city of Königsberg, Germany, there is a part of the city surrounded by a river, which flows away in three directions. There are seven bridges in the city. Here, use this image as a reference:

Euler, a mathematician, posed the following problem: is it possible to navigate a path through the city crossing each of these bridges once and only once? Assume you're not allowed to cross the river unless it is via one of the bridges above. Spoiler: you can't do it. There's a proof of why that I used to know several years ago, as a young man growing up on the mean streets of Milwaukee, but those days are over. Now I'm more interested in this problem's taking a very geographically-based network and removing it from geography.

This is the same map as above, only with all geographic references taken out. You can't see your house from here, but you sure can try to find a path across the bridges. Here the yellow dots represent regions of the city, and the lines connecting the dots represent paths across bridges. I'm interested in doing something similar on a large scale, say, the US Interstate System. We'll talk in class! I'll probably repeat exactly what I say here because we're just going to look at the pictures! Excellent!

Posted by Scott.