The seven bridges of Königsberg
Königsberg had four land masses, two river banks and two islands. One island was joined to each bank by two bridges, the other island to each bank by one bridge, and a seventh bridge joined the two islands. Is there a walk that crosses every bridge exactly once? More generally, which connected graphs have a walk that uses every edge exactly once?
History and references
Solved in 1736 by Leonhard Euler.
Euler analyzed the puzzle in 1736, and his solution is usually taken as the beginning of graph theory. He saw that only the land masses and the bridges between them matter, not the exact route. Every time a walk passes through a land mass it uses two bridges, so every land mass other than the start and the end must touch an even number of bridges. In Königsberg one land mass touches 5 bridges and the other three touch 3 each, so no such walk exists. The general criterion, that a connected graph has such a walk exactly when it has zero or two vertices of odd degree, was stated by Euler and later proved in full by Carl Hierholzer.
References
Solutions 0
Sign in or create an account to publish a solution