The Bridges of Königsberg

In the eighteenth century, the Prussian city of Königsberg sat at a fork in the Pregel River, its four landmasses stitched together by seven bridges. A local puzzle asked: can you take a walk that crosses each bridge exactly once?

The citizens tried and failed. In 1736, the Swiss mathematician Leonhard Euler explained why failure was inevitable — and in doing so invented the branch of mathematics now called graph theory.

Euler's key move was to stop caring about streets, distances, and geography. He replaced the map with an abstract object: landmasses became vertices, bridges became edges, and the question became purely about the structure of connections. That abstraction — seeing through the surface to the underlying pattern — is one of the most powerful ideas in all of mathematics.

Below is the Königsberg graph: four landmasses (vertices) connected by seven bridges (edges). Click edges in order to trace a walk. Can you cross every bridge exactly once?

<!-- {{c_intro}} -->
<div class="layout">
  <div class="left-panel">
    <p class="hint">{{hint_para}}</p>
    <svg id="graph" viewBox="0 0 300 280" width="300" height="280" aria-label="{{aria_graph}}">
      <!-- {{c_edges_comment}} -->
      <!-- {{c_edge_ab1}} A(island) <-> B(north bank), bridge 1 -->
      <line id="e-AB1" class="edge" x1="150" y1="130" x2="150" y2="48" data-from="A" data-to="B"/>
      <!-- {{c_edge_ab2}} A(island) <-> B(north bank), bridge 2 -->
      <path id="e-AB2" class="edge path-edge" d="M150,130 Q120,88 150,48" fill="none"/>
      <!-- {{c_edge_ac1}} A(island) <-> C(east bank), bridge 3 -->
      <line id="e-AC1" class="edge" x1="150" y1="150" x2="252" y2="160" data-from="A" data-to="C"/>
      <!-- {{c_edge_ac2}} A(island) <-> C(east bank), bridge 4 -->
      <path id="e-AC2" class="edge path-edge" d="M150,165 Q200,200 252,168" fill="none"/>
      <!-- {{c_edge_ad}} A(island) <-> D(south bank), bridge 5 -->
      <line id="e-AD" class="edge" x1="150" y1="165" x2="150" y2="240" data-from="A" data-to="D"/>
      <!-- {{c_edge_bd}} B(north bank) <-> D(south bank), bridge 6 -->
      <path id="e-BD" class="edge path-edge" d="M138,50 Q40,148 138,240" fill="none"/>
      <!-- {{c_edge_cd}} C(east bank) <-> D(south bank), bridge 7 -->
      <line id="e-CD" class="edge" x1="252" y1="168" x2="150" y2="242" data-from="C" data-to="D"/>
      <!-- {{c_vertices_comment}} -->
      <!-- A = Kneiphof island (center) -->
      <circle class="vertex" cx="150" cy="148" r="24"/>
      <!-- B = north bank -->
      <circle class="vertex" cx="150" cy="42" r="18"/>
      <!-- C = east bank (Lomse island) -->
      <circle class="vertex" cx="258" cy="163" r="18"/>
      <!-- D = south bank -->
      <circle class="vertex" cx="150" cy="248" r="18"/>
      <!-- {{c_vertex_labels}} -->
      <text class="vlabel" x="150" y="153">A</text>
      <text class="vlabel" x="150" y="47">B</text>
      <text class="vlabel" x="258" y="168">C</text>
      <text class="vlabel" x="150" y="253">D</text>
    </svg>
    <div class="status" id="status">{{status_start}}</div>
    <div class="btns">
      <button id="undo" type="button">{{btn_undo}}</button>
      <button id="reset" type="button" class="ghost">{{btn_reset}}</button>
    </div>
  </div>
  <div class="right-panel">
    <h3 class="panel-title">{{panel_degrees}}</h3>
    <table id="degree-table">
      <thead><tr><th>{{col_land}}</th><th>{{col_bridges}}</th><th>{{col_parity}}</th></tr></thead>
      <tbody></tbody>
    </table>
    <p class="euler-rule" id="euler-msg"></p>
  </div>
</div>

/* {{c_css_intro}} */
* { box-sizing: border-box; }
body { font-family: system-ui, sans-serif; color: #222; margin: 0; }
.layout { display: flex; gap: 1.2rem; flex-wrap: wrap; }
.left-panel { flex: 0 0 auto; }
.right-panel { flex: 1 1 180px; min-width: 160px; }
.hint { font-size: .88rem; color: #444; margin: 0 0 .6rem; line-height: 1.45; max-width: 300px; }
/* {{c_css_edge}} */
.edge { stroke: #9fb2c8; stroke-width: 7; stroke-linecap: round; cursor: pointer; transition: stroke .15s; }
.edge:hover { stroke: #5a7088; }
.edge.used { stroke: #e63946; }
.edge.disabled { pointer-events: none; }
/* {{c_css_vertex}} */
.vertex { fill: #1d3557; stroke: none; }
.vlabel { fill: #fff; font: 700 14px system-ui, sans-serif; text-anchor: middle; dominant-baseline: middle; pointer-events: none; }
.status { font-size: .95rem; font-weight: 600; margin: .5rem 0; min-height: 1.4em; }
.status.ok { color: #0a7d33; }
.status.bad { color: #c92f3c; }
.status.info { color: #1d3557; }
.btns { display: flex; gap: .5rem; margin-top: .3rem; }
button { font: 600 14px system-ui; padding: .4rem .85rem; border: 1px solid #1d3557;
         background: #1d3557; color: #fff; border-radius: 8px; cursor: pointer; }
button.ghost { background: #fff; color: #1d3557; }
button:disabled { opacity: .4; cursor: default; }
/* {{c_css_table}} */
.panel-title { font-size: .9rem; font-weight: 700; margin: 0 0 .4rem; color: #1d3557; }
table { border-collapse: collapse; width: 100%; font-size: .85rem; }
th, td { padding: .3rem .5rem; text-align: center; border-bottom: 1px solid #dde3ea; }
th { background: #e8eef3; font-weight: 700; }
td.odd { color: #c92f3c; font-weight: 700; }
td.even { color: #0a7d33; }
.euler-rule { font-size: .82rem; line-height: 1.45; color: #444; margin: .6rem 0 0; }

// Code not found

Notice the degree panel on the right — it shows how many bridges touch each landmass. Euler's theorem says: an Eulerian walk (crossing every edge exactly once) is possible if and only if the graph has zero or two odd-degree vertices. Königsberg has four odd-degree vertices, so no such walk can exist.

The Königsberg problem sits at a remarkable crossroads in computational thinking.

• Euler's theorem (1736): an Eulerian walk (visiting every edge exactly once, returning to the start is optional) exists if and only if the graph is connected and has zero or two odd-degree vertices. Zero odd-degree vertices means you return to your starting point (an Eulerian circuit); exactly two means you start at one and end at the other.
• Deciding the problem is easy: compute the degree of every vertex in $O(V + E)$ time and count the odd-degree ones. This is one of the earliest examples of a mathematical puzzle that has a clean, fast algorithmic answer.
• Finding the actual path is also easy: Hierholzer's algorithm finds an Eulerian circuit in $O(V + E)$ time by greedily walking until stuck, then stitching sub-tours together.
• Contrast with Hamiltonian paths: replace "every edge" with "every vertex" and the problem — does a Hamiltonian path exist? — becomes NP-complete. Two problems that sound nearly identical diverge completely in difficulty.

Euler's clean criterion — count odd-degree vertices — works because it captures the local constraint that must hold at every intermediate vertex: every time you enter, you must be able to leave. An odd-degree vertex has no such escape if it is neither the start nor the end. The global impossibility follows from a purely local observation.

The abstraction Euler invented — reduce a map to vertices and edges, then reason about structure alone — is the foundation of modern graph theory. The Eulerian path condition in particular turns up in surprising places:

• Circuit board routing: a PCB must route copper traces that connect every component without redundant passes; this is exactly an Eulerian path problem on the routing graph.
• DNA sequencing (de Bruijn graphs): genome assemblers model short read fragments as edges in a graph and reconstruct the genome by finding an Eulerian path through it.
• Street-sweeping and postman problems: a garbage truck or mail carrier that must traverse every street at least once looks for an Eulerian circuit, adding minimum-cost duplicate edges where odd-degree vertices exist (the Chinese Postman Problem).
• Transition systems and test coverage: ensuring that every transition in a finite automaton is exercised at least once is an Eulerian path problem on the state graph — a key idea in software testing.

The lesson generalises far beyond bridges. Any time you need to visit every connection in a network exactly once, you are asking Euler's question — and his 1736 answer still gives you the fastest possible check. For more on how graph structure decides what is easy versus hard, see Euler vs Hamilton.

Euler did not solve the Königsberg puzzle — he proved it was unsolvable, and in doing so demonstrated something far more powerful: by stripping a physical problem down to its abstract skeleton, you can sometimes answer it completely and forever.

The odd-degree rule is a perfect example of a local condition implying a global impossibility. You do not need to try every possible route. You just count. The four odd-degree vertices in Königsberg doom every walk before it starts, no matter how clever the traveller.

That shift from "try all paths" to "check a simple structural property" is the hallmark of good algorithm design — and it began on a riverside in Prussia in 1736.