[This post also appears as a guest post over at Sam Shah's blog.]

This is a post about a problem that never fails. It’s the problem I used for my sample lesson when interviewing for jobs four years ago. It’s the one I almost always use on the first day of class, and it’s also what I give to parents on back to school night. Because… well…**it.** **never. fails**. Seriously.

The perfect, ineffable jewel of a problem to which I refer is the classic Bridges of Konigsberg problem. Here’s the story, in case you don’t know it:

- (image from wikipedia)

As shown in the image above, the town of Konigsberg once had seven bridges. Back before some of these bridges were bombed during WWII, the residents of the town had a long-standing challenge: to walk through the town in such a way that you crossed each bridge exactly once—i.e., without missing any bridges, and without crossing any of them twice.

So, why is this problem so great for a high school classroom? Well, first of all, whenever I tell this rather contrived tale to my students (or their parents, for that matter), they are inevitably scribbling on their scrap paper before I can even finish. It’s a compelling puzzle, simple as that.

Before long, students have redrawn the thing enough times that they’re annoyed with all the extra time it takes to draw all the landmasses and bridges, and so they simplify it:

- (image from wikipedia)

Voila: in a completely natural fashion, they have reduced the problem just like Euler did. At this point, I usually bring them together for a moment to appreciate what’s going on here: reducing a problem to its essential components, finding the simplest way to represent the underlying structure of the situation. (And I also mention to them that this is precisely the move that Euler made when he invented graph theory based on this initial problem.) Even if they never went any further, this is already a nice lesson in problem solving.

**[SPOILER ALERT: notes on the solution below the fold]**

Continue reading →