A Famous Bridge Problem
So I looked in the back of our geometry textbook, curious to see what was there — hadn't ventured this far back before and because we'd just finished with the State tests — and I saw the Königsberg Bridge problem!
I was all excited because what little I know about graph theory I find very interesting and useful. I found three lessons under the heading Discrete Mathematics:
A Famous Bridge Problem, pages 676-678
A Traveler's Puzzle, pages 678-681
Minimizing the Cost of a Network, pages 681-683
I thought, This could be my geometry lesson for the entire week!!
But half way through reading the first page of A Famous Bridge Problem, I came to this paragraph:
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 a lot worse, actually.
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, giving the 9 bridges as shown at the right, then every vertex has an even valence, and a circuit over all 9 bridges is possible.
Then, finally, right before the Exercises section on the next page, a question is posed:
Can you find an Euler circuit for the graph of the 9-bridges problem?
The answer to this question, printed in my teacher's edition, is Yes.
What?!! Really?!! This textbook just gave away the answer [... so a circuit over all 7 bridges is impossible] to what I thought would be a natural first question that I would pose to my kids: Can you walk in the city of Königsberg so that you will cross each bridge exactly once?
Just like that, in one swift sentence [... every vertex must have an even valence], McDougal Littell not only gave the answer but also decided not to give students an opportunity to reason it out for themselves.
I searched Google and picked this image, copied and pasted onto a Word document with nothing else on it.
I gave the students a brief history on the Königsberg Bridge problem and reintroduced them to Euler.
Question #1: Can you walk in the city of Königsberg so that you will 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 answered NO to the first question. What they said and what their papers looked like:
(Many): I tried a few times, can't get it to work. I'll try a couple more times.
Michael: You'd have to have equal number of bridges evenly.
Bobby: I know I said yes, but I can't replicate, repeat it.
I had students number the bridges, then I posed question #2: What if bridge 2 got destroyed, no longer there, can you walk in this city so that you will cross the remaining six bridges exactly once?
Again, they tested more routes and wrote NO for their answer.
Question #3: Suppose a new bridge gets built to replace the collapsed bridge 2, where should it be built so a person can walk through the city crossing each bridge exactly once.
Michael: I perfected my theory!
Me: What was your theory?
Someone said something to him that I couldn't hear.
Michael: Okay, maybe not. But I discovered something else.
This is a clip of Michael explaining his thinking.
Slater explained why he'd build a new bridge next to (parallel to) bridge 4.
It made me happy that Austin called me over so he could explain his answer. Normally he's shy about sharing his work.
Colin made more sketches than anyone else. He tried a lot of different paths, and this is him explaining his placement of the new bridge.
I recorded all the possible placements of the new bridge (to replace bridge 2) on my sketch on the projector — there were 5 different locations that were shared.
Bobby normally is slow to leave class, today was no exception. He came up to the board and started talking.
Tomorrow we'll talk about vertices and edges and valence and convert our Königsberg Bridge into a network diagram. We'll practice drawing and exploring more of these diagrams. And maybe my kids will generalize that "every vertex must have an even valence." And maybe they won't. But I think today I gave my kids a chance to think about math in their own language.