Königsberg bridges: the walk that became a network
The Königsberg bridges connected four land regions through seven crossings. Leonhard Euler showed that a walk could not cross each bridge exactly once. The obstacle lay in how the bridges met the land, rather than their lengths or the distances across town. His analysis replaced the geographical details with letters recording regions and transitions between them. A recreational walk became an investigation of connection patterns, part of the development of graph theory. [1, 2, 3]
The city stood on the River Pregel, with the island of Kneiphof among the separated regions. Euler labeled the four regions A, B, C and D. Two bridges connected A with B, and two connected A with C. Single bridges joined A with D, B with D, and C with D. The bridge labels distinguished crossings that linked the same pair of regions. A list of region names could record a walk while the number of available bridges restricted how often each transition occurred. [1]
In that notation, crossing from A to B produces AB. Continuing from B to D produces ABD, using three letters for two bridge crossings. Seven successive crossings would need eight letters. Region A had five incident bridges, requiring its letter to appear three times in such a complete route. Each other region had three incident bridges and required two appearances. The necessary appearances total nine, exceeding the eight positions available. [1]
This letter count allowed Euler to reject the complete walk without listing every route. His paper considered more general distributions of islands, river branches and bridges. One further example had six regions and fifteen bridges. Two regions had odd bridge counts, while the other four had even counts. Euler’s tabulation treated even and odd numbers differently when calculating how often a region would occur in the route. The Königsberg bridges supplied one instance of a larger classification. [1]
Modern graph language replaces each land region with a vertex and each bridge with an edge. A vertex’s degree counts its incident edges. Traveling through a vertex uses edges in pairs: one arrival and one departure. A closed journey pairs them at its starting point as well. Consequently, a connected network can have a closed route using every edge exactly once only when every vertex has even degree. [3, 4]
A journey with different starting and finishing points has two exceptions. Its beginning has one extra departure, and its ending has one extra arrival. Exactly two vertices then have odd degree, and those vertices must be the endpoints. The Königsberg network has four odd-degree vertices: one of degree five and three of degree three. It therefore permits neither a closed circuit nor an open trail using all seven edges just once. [1, 3, 4]
The historical dates require a distinction between writing and publication. Euler’s Latin work, Solutio problematis ad geometriam situs pertinentis, was written in 1735 and published in 1741. It appeared in volume eight of the St Petersburg Academy’s Commentarii, occupying printed pages 128 through 140. The volume is associated with 1736, a date often attached to the result. The Euler Archive separately records 1735 as the written date and 1741 as the publication date. [1, 2]
Carl Hierholzer’s later method constructs circuits by joining smaller circuits. In an eligible network, it begins at a vertex and follows unused edges until returning to its beginning. If unused edges remain at a vertex on that circuit, a second circuit can begin there. The new circuit uses no edge of the earlier one. Its sequence can be inserted at their shared vertex, making a longer circuit through the combined edge collection. [3, 4]
Further unused edges lead to further insertions. The process ends when the assembled route includes all the edges. Choosing an odd-degree endpoint adapts the construction to an eligible open trail. In a directed network, the distinction between incoming and outgoing edges matters as well. A closed route requires equal incoming and outgoing counts at each vertex; an open route has a start with one extra outgoing edge and an end with one extra incoming edge. [4]
Euler’s further network contrasts with the Königsberg bridges: its six regions have bridge counts of eight, four, four, three, five and six. Only the regions with three and five have odd counts. They supply the starting and finishing regions of an open journey through all fifteen bridges. [1]
One-stroke drawing has the same underlying restriction. Its intersections and line segments can form a network, and tracing each segment once corresponds to an edge-by-edge journey. Returning to an intersection is allowed; repeating an edge is the excluded action. The bridge analysis and the circuit-construction method address complementary parts of this structure: the degree counts determine whether a route is possible, and a construction organizes the route when the conditions are met. [3, 4]
[1] Leonhard Euler, Solutio problematis ad geometriam situs pertinentis, primary text. https://www.cantab.net/users/michael.behrend/repubs/maze_maths/pages/euler.html
[2] University of the Pacific Euler Archive, E53: written and publication dates. https://scholarlycommons.pacific.edu/euler-works/53/
[3] ETH Zurich Library, Königsberg-Brücken: Euler, Hierholzer and one-stroke drawing. https://library.ethz.ch/sammlungen-und-archive/online-zugaenge/virtuelle-ausstellungen/alles-ist-spiel/koenigsberg-bruecken.html
[4] Technical University of Munich, Hierholzer’s Algorithm: graph conditions and cycle splicing. https://m09vm26.ma.tum.de/graph-algorithms/hierholzer/index_en.html