Bridges of Königsberg
A question arose among the town's curious citizens: Was it possible to make a journey across all seven bridges without having to cross any bridge more than once? No one had been able to do it, but was there a solution? Euler, who was in St. Petersburg, Russia, at the time, heard about this puzzle and looked into it. In 1736 he published a paper called Solutio problematis ad geometriam situs pertinentis (The solution of a problem relating to the geometry of position) in which he gave his answer. Euler reasoned that, for such a journey to be possible, each land mass would need to have an even number of bridges connected to it, or, if the journey began at one land mass and ended at another then those two land masses alone could have an odd number of connecting bridges while all the other land masses would have to have an even number of connecting bridges. Since the Königsberg bridges violated this layout, a grand tour that involved only one crossing per bridge was impossible. Euler's paper was important because it solved not just the Königsberg conundrum but the much more general case of any network of points, or vertices, that are connected by lines, or arcs. What is more, the words "geometry of position" in the title shows that Euler realized that he was dealing with a different type of geometry where distance is irrelevant; so this work can be seen as a prelude to the subject of topology.
Related entry Euler path
Related categories GAMES AND PUZZLES
GRAPHS AND GRAPH THEORY
Home • About • Copyright © The Worlds of David Darling • Encyclopedia of Alternative Energy • Contact