Seven Bridges of Königsberg

The Seven Bridges of Königsberg problem asks whether a walk can cross each of the city’s seven bridges exactly once. Leonhard Euler proved no such walk exists, helping establish graph theory.

Eulerian path: A trail in a graph that uses every edge exactly once. The proposed bridge walk is an Eulerian path in the graph representing Königsberg.
Leonhard Euler: A Swiss mathematician whose work shaped analysis, number theory, mechanics, and graph theory. Euler gave the 1736 proof that no route crosses every bridge exactly once.
Route inspection problem: The problem of finding a shortest closed route that traverses every edge of a network. It generalizes bridge-crossing puzzles by allowing repeated edges to complete a practical route.
Topology: The study of properties preserved under continuous deformation. Euler’s abstraction preserved connections while ignoring the bridges’ lengths and shapes.
Graph theory: The mathematical study of graphs, structures made of vertices connected by edges. Euler’s bridge abstraction helped launch this field.
Königsberg: The former Prussian city now known as Kaliningrad, Russia. Its river, islands, and seven bridges formed the problem’s physical setting.
Chinese postman problem: A graph optimization problem seeking the shortest closed walk that traverses every edge. It formalizes efficient inspection routes when an Eulerian circuit does not already exist.
Network science: The study of structures and processes in interconnected systems. The land-and-bridge model anticipates the network representations used across modern sciences.
Vertex degree: The number of edges incident to a vertex in a graph. Each landmass’s degree counts how many bridges meet it.
Pregel: A river in the former East Prussian region that flows through Kaliningrad. The Pregel divided Königsberg into landmasses connected by the bridges.

Linked from 9 pages