Introduction

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.

Try to Cross Them All

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?

<!-- Königsberg bridge-crossing demo: interactive graph traversal -->
<div class="layout">
  <div class="left-panel">
    <p class="hint">Click edges (bridges) in order to trace a walk. Try to cross every bridge exactly once. The degree table shows how many bridges touch each landmass — spot the 4 odd-degree vertices!</p>
    <svg id="graph" viewBox="0 0 300 280" width="300" height="280" aria-label="Königsberg bridge graph">
      <!-- Graph edges — each SVG element represents one bridge -->
      <!-- Bridge 1 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"/>
      <!-- Bridge 2 A(island) <-> B(north bank), bridge 2 -->
      <path id="e-AB2" class="edge path-edge" d="M150,130 Q120,88 150,48" fill="none"/>
      <!-- Bridge 3 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"/>
      <!-- Bridge 4 A(island) <-> C(east bank), bridge 4 -->
      <path id="e-AC2" class="edge path-edge" d="M150,165 Q200,200 252,168" fill="none"/>
      <!-- Bridge 5 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"/>
      <!-- Bridge 6 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"/>
      <!-- Bridge 7 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"/>
      <!-- Vertex circles: A=Kneiphof island (center), B=north bank, C=east bank, D=south bank -->
      <!-- 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"/>
      <!-- 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">Click a bridge to start your walk.</div>
    <div class="btns">
      <button id="undo" type="button">Undo</button>
      <button id="reset" type="button" class="ghost">Reset</button>
    </div>
  </div>
  <div class="right-panel">
    <h3 class="panel-title">Vertex degrees</h3>
    <table id="degree-table">
      <thead><tr><th>Land</th><th>Bridges</th><th>Parity</th></tr></thead>
      <tbody></tbody>
    </table>
    <p class="euler-rule" id="euler-msg"></p>
  </div>
</div>

/* Layout and visual styles for the Königsberg demo */
* { 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; }
/* Bridge (edge) styling: gray by default, red when used */
.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; }
/* Landmass (vertex) styling: dark blue circles with white labels */
.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; }
/* Degree table styling */
.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; }

const i18nFmt = (s, v) => s.replace(/%(\w+)%/g, (_, k) => String(v[k] ?? ''));
// Interactive Königsberg bridge-crossing demo
// Graph definition: 4 vertices (landmasses) and 7 edges (bridges)
const VERTICES = ['A', 'B', 'C', 'D'];
// Correct Königsberg edges: A-B x2, A-C x2, A-D x1, B-D x1, C-D x1 => degrees A=5,B=3,C=3,D=3 => all odd
const EDGES = [
  { id: 'e-AB1', from: 'A', to: 'B' },
  { id: 'e-AB2', from: 'A', to: 'B' },
  { id: 'e-AC1', from: 'A', to: 'C' },
  { id: 'e-AC2', from: 'A', to: 'C' },
  { id: 'e-AD',  from: 'A', to: 'D' },
  { id: 'e-BD',  from: 'B', to: 'D' },
  { id: 'e-CD',  from: 'C', to: 'D' }
];

// Degree verification comment
// Degrees: A=5, B=3, C=3, D=3 => all 4 vertices are odd => no Eulerian walk.

// Walk state: set of used edge ids, ordered history, and current endpoint
const used = new Set();
const history = [];
let currentVertex = null;

// Compute current degree of each vertex counting only unused edges
function degrees() {
  const d = {};
  VERTICES.forEach(v => d[v] = 0);
  EDGES.forEach(e => {
    if (used.has(e.id)) return;
    d[e.from]++;
    d[e.to]++;
  });
  return d;
}

function renderDegrees() {
  const d = degrees();
  const tbody = document.querySelector('#degree-table tbody');
  tbody.innerHTML = '';
  VERTICES.forEach(v => {
    const deg = d[v];
    const parity = deg % 2 === 0 ? 'even' : 'odd';
    const cls = deg % 2 === 0 ? 'even' : 'odd';
    tbody.innerHTML += `<tr><td><b>${v}</b></td><td>${deg}</td><td class="${cls}">${parity}</td></tr>`;
  });
  // Display Euler’s theorem verdict based on current odd-degree count
  const odd = VERTICES.filter(v => d[v] % 2 !== 0).length;
  const msg = document.getElementById('euler-msg');
  if (odd === 0) {
    msg.textContent = i18nFmt('%odd% odd-degree vertices — Eulerian circuit possible (can return to start).', { odd });
  } else if (odd === 2) {
    msg.textContent = i18nFmt('%odd% odd-degree vertices — Eulerian path possible (start ≠ end).', { odd });
  } else {
    msg.textContent = i18nFmt('%odd% odd-degree vertices — No Eulerian walk possible!', { odd });
  }
}

function setStatus(t, cls) {
  const s = document.getElementById('status');
  s.textContent = t;
  s.className = 'status ' + (cls || '');
}

function useEdge(edge) {
  if (used.has(edge.id)) return;
  // Each new edge must touch the current vertex (walk must be continuous)
  if (currentVertex !== null && edge.from !== currentVertex && edge.to !== currentVertex) {
    setStatus('That bridge doesn’t connect to your current position.', 'bad');
    return;
  }
  used.add(edge.id);
  history.push(edge.id);
  // Advance currentVertex to the other end of the edge just traversed
  if (currentVertex === null) {
    currentVertex = edge.to;
  } else {
    currentVertex = (edge.from === currentVertex) ? edge.to : edge.from;
  }
  renderEdges();
  renderDegrees();
  checkCompletion();
}

function renderEdges() {
  EDGES.forEach(e => {
    const el = document.getElementById(e.id);
    if (!el) return;
    if (used.has(e.id)) {
      el.classList.add('used', 'disabled');
    } else {
      el.classList.remove('used', 'disabled');
    }
  });
  document.getElementById('undo').disabled = history.length === 0;
}

function checkCompletion() {
  if (used.size === EDGES.length) {
    setStatus('You crossed all 7 bridges — impressive routing! (In the real Königsberg this is impossible.)', 'ok');
  } else if (used.size > 0) {
    setStatus(i18nFmt('%used% of %total% bridges crossed.', { used: used.size, total: EDGES.length }), 'info');
  } else {
    setStatus('Click a bridge to start your walk.', '');
  }
}

function undo() {
  if (history.length === 0) return;
  const lastId = history.pop();
  used.delete(lastId);
  // Replay history from scratch to recover currentVertex after an undo
  currentVertex = null;
  history.forEach(id => {
    const edge = EDGES.find(e => e.id === id);
    if (currentVertex === null) {
      currentVertex = edge.to;
    } else {
      currentVertex = (edge.from === currentVertex) ? edge.to : edge.from;
    }
  });
  renderEdges();
  renderDegrees();
  checkCompletion();
}

function reset() {
  used.clear();
  history.length = 0;
  currentVertex = null;
  renderEdges();
  renderDegrees();
  setStatus('Click a bridge to start your walk.', '');
}

// Attach click handlers and render initial state
EDGES.forEach(e => {
  const el = document.getElementById(e.id);
  if (el) el.addEventListener('click', () => useEdge(e));
});
document.getElementById('undo').addEventListener('click', undo);
document.getElementById('reset').addEventListener('click', reset);
renderEdges();
renderDegrees();
setStatus('Click a bridge to start your walk.', '');
Result
Console

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 Real Complexity

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)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)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.

Where It Matters

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.

Conclusion

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.

Share this article

Pick a channel — or use your device's native share sheet.

Comments

Loading comments...

https://www.kipuhub.com/en/article/bridges-of-konigsberg/Content licensed under CC BY-NC 4.0.