Linked

Connecting the Dots

Until 1875, the branches of the Pregel River split the city of Königsberg, Prussia, into four pieces. Seven bridges connected the pieces: Five crossed to an island in the middle of the river and two crossed branches of the river. These bridges gave rise to the following puzzle: "Could one walk across all seven bridges of Königsberg without crossing the same one twice?" No one could solve this puzzle, not even the brilliant Swiss-born mathematician Leonhard Euler. But in 1736, while trying to solve it, Euler discovered why people had been working on the problem for so long: The Königsberg Bridge puzzle was not solvable. With this proof of insolubility, Euler created a new branch of mathematics called “graph theory.”

A graph is a simple diagram resembling a child's connect-the-dots game. Euler reduced the Königsberg Bridge problem to dots and lines or, in the jargon of graph theory, nodes and links. He represented the four landmasses as nodes, drawing a dot for each. He represented the bridges as lines linking the dots. On paper, the graph of the Königsberg Bridge problem looks nothing like a Prussian city on a river. Rather, it looks a bit like a...