Parades – 2 – 7 Bridges of Königsberg
This is a map of Königsberg showing the river that runs through it, the island in the middle of the river, and the seven bridges that span the river. The people of Königsberg wanted to have a parade that went over each of their bridges exactly once. They could not seem to find a parade route that visited all seven bridges.
THE CHALLENGE
If you can, find a parade route that crosses each of their bridges exactly once. If you can’t, give a reason for why it is impossible.
EXPLORATION
If you add another bridge over the river, would that make the problem easier or harder?
Notes
THE CHALLENGE
Start by translating this problem into one that has edges we need to traverse. We saw in the earlier “Parades” Puzzle of the Week that it is crucial to have no more than two nodes where an odd number of sides come in.
Because all four of the nodes have an odd number of edges coming into them, it will be impossible to find a parade route!
EXPLORATION
If you add one more bridge across the river anywhere, you will make it very easy to solve
this problem. That’s because two of the four nodes will then have an even number of edges coming into them,
and that will leave only two nodes with an odd number of edges coming into them.