Seven Bridges of Königsberg/key
From Wikipedia, the free encyclopedia
Contents |
[edit] Solution to the variant Königsberg
[edit] Answer
[edit] Solution
Reduce the city, as before, to a graph. Color each node. As in the classic problem, no Euler walk is possible; coloring does not affect this. All four nodes have an odd number of edges.
[edit] The Blue Prince's 8th bridge
Euler walks are possible if exactly 2 nodes have an odd number of edges. If this is so, then the walk must begin at one such node and end at the other. Since there are only 4 nodes in the puzzle, solution is simple. The walk is desired to begin at the blue node and end at the beer-colored node. Thus a new edge is drawn between the other two nodes. Since they each formerly had an odd number of edges, they must now have an even number of edges, fulfilling all conditions. This is a change in parity from odd to even degree.
[edit] The Red Prince's 9th bridge
The 9th bridge is easy once you've solved the 8th. It is desired to enable the red and forbid the blue as a starting point; the beer-colored node remains the end of the walk and the white node is unaffected. To change the parity of both red and blue nodes, draw a new edge between them.
[edit] The Bishop's 10th bridge
The 10th bridge takes us in a slightly different direction. The Bishop wishes every citizen to return to his starting point. This is an Euler cycle and requires that all nodes are of even degree. After the solution of the 9th bridge, the red and the beer-colored nodes have odd degree, so they must be changed by adding a new edge between them.
