A Famous Bridge Problem
Originally posted May 14, 2013
I was flipping through the back of our geometry textbook — hadn’t ventured that far before, and we’d just finished State testing — when I saw the Königsberg Bridge problem!
I got all excited. The little I know about graph theory, I find really interesting and useful. I found three lessons under the heading Discrete Mathematics:
A Famous Bridge Problem, pp. 676–678
A Traveler’s Puzzle, pp. 678–681
Minimizing the Cost of a Network, pp. 681–683
I thought, This could be my geometry lesson for the entire week!
But halfway through reading the first page of A Famous Bridge Problem, I hit this:
Euler reasoned that in order for a person to travel every bridge once and return to the starting point, every vertex must have an even valence. This is because a person traveling into a vertex must also leave it. So the edges must be paired, one "in" with one "out."
It got better. Or worse, depending on how you look at it:
In the 7-bridges problem, none of the vertices has an even valence, so a circuit over all 7 bridges is impossible. However, if two more bridges were added... then every vertex has an even valence, and a circuit over all 9 bridges is possible.
Then, right before the Exercises section:
Can you find an Euler circuit for the graph of the 9-bridges problem?
The answer in the teacher edition?
Yes.
What?!! Really?!!
The book just gave away the answer to what I thought would be a natural first question for my students:
Can you walk in the city of Königsberg and cross each bridge exactly once?
Just like that, in one sentence, McDougal Littell killed the mystery and the thinking. No opportunity for students to reason through it.
So I searched Google and found a clean image of the bridge layout. I pasted it into a Word doc — nothing else — and printed it.
I gave students a brief history of the Königsberg Bridge problem and reintroduced them to Euler.
Question 1: Can you walk in the city of Königsberg and cross each bridge exactly once?
Bobby: Yes!
Josh: This is too hard!
Jacob: Don’t say that. Mrs. Nguyen loves it when we say that!
Zach: The answer is no.
Taj: No.
I walked around the room. All but two students eventually answered NO to the first question.
Some comments:
“I tried a few times, can’t get it to work. I’ll try a couple more.”
“You’d have to have an equal number of bridges evenly.”
“I know I said yes, but I can’t replicate it.”
Then I asked:
Question 2: What if bridge #2 is destroyed — can you now cross each of the remaining 6 bridges exactly once?
Again, lots of testing. Again, NO was the consensus.
Question 3: Suppose a new bridge is built to replace bridge 2. Where should it be placed so a person can cross each bridge exactly once?
Michael: “I perfected my theory!”
Me: “What’s your theory?”
(Someone mutters something to him.)
Michael: “Okay, maybe not. But I discovered something else.”
I recorded his explanation.
Slater shared his reasoning for adding a bridge parallel to bridge 4.
Austin — normally shy — called me over to explain his answer.
Colin made the most sketches, trying many paths.
I drew all their proposed bridge placements on the projector. We had five different suggestions.
Bobby was, as usual, slow to leave class. He came up to the board and kept talking through it.
Tomorrow, we’ll introduce vertices, edges, valence, and convert our Königsberg bridge map into a network diagram. We’ll draw more graphs and explore. And maybe, just maybe, they’ll generalize that “every vertex must have an even valence.” Or maybe they won’t. Either way, I think today they got to think about math in their own language.