On the graph-theoretic, spectral, and topological analysis of the Seven Bridges of Königsberg
A formal synthesis of the Seven Bridges of Königsberg, Euler's founding result of 1736, carried into modern language: adjacency, incidence, and Laplacian matrix representations give a self-contained proof of impossibility; the full Laplacian spectrum and eigenbasis, Kirchhoff network flows, and the Kirchhoff index quantify structural efficiency; and two bridge additions — the historical Kaiserbrücke of 1905 and a provably minimal two-bridge Eulerisation — are analyzed exactly.
1 · Euler's 1736 impossibility
Model the four landmasses of Königsberg as vertices A, B, C, D and the seven bridges as a multigraph. Every vertex has odd degree — the North Bank, Kneiphof Island, the South Bank, and the East Landmass carry degrees 3, 5, 3, 3 — so by the Euler–Hierholzer theorem no walk crossing each bridge exactly once can exist, from any starting point. The conclusion falls out of the adjacency matrix alone: only the pattern of connections matters, not the geography.
2 · The Laplacian and Kirchhoff flow
Treating each bridge as a unit-resistance conductor, the graph Laplacian L = D − A equals SSᵀ for the signed incidence matrix S. Injecting 100 units of flow at the North Bank and extracting it at the South Bank, grounding C, Cramer's rule gives exact nodal potentials: the source A sits highest, while B and D — both adjacent to the sink — settle at an equal, lower potential.
3 · Spectrum and the Kirchhoff index
The Laplacian spectrum is (0, 3, 4, 7): the Fiedler value 3 separates North Bank from South Bank, and the top eigenvalue concentrates at Kneiphof Island, the network's spectral bottleneck. The Kirchhoff index K = 4(1/3 + 1/4 + 1/7) = 61/21 ≈ 2.905 measures global efficiency. Removing one of the two parallel A–B bridges costs 19.2% in effective resistance; removing the unique A–D bridge costs 41.1% — parallel edges are structural redundancy a lone bridge cannot provide.
4 · Adding bridges: 1905 and minimal Eulerisation
The historical Kaiserbrücke of 1905, an eighth bridge parallel to C–D, leaves exactly two odd vertices and creates an open Eulerian trail from A to B — the first traversable network since the city's founding — while cutting effective resistance by 12.9%. A closed circuit is impossible with one bridge: each new edge repairs at most two odd vertices, so at least k/2 = 2 are needed. Adding bridges A–C and B–D achieves this minimum, yields a closed Eulerian circuit over all nine bridges, and delivers the largest efficiency gain of any variant studied: 27.7%.