THE EULER PATH — a dart

THE EULER PATH every bridge once — the walk that founded graph theory

In 1736 Leonhard Euler asked whether you could walk the seven bridges of Königsberg, crossing each exactly once, and proved you could not — founding graph theory with the answer. An Euler path (every edge once) exists in a connected graph if and only if it has 0 or 2 odd-degree vertices; an Euler circuit (returning to start) needs 0. The reason is beautiful: every time you pass through a vertex you use two edges (in and out), so interior vertices need even degree — only the start and end may be odd. Königsberg had four odd vertices, so no walk existed. This graph has exactly 2 odd vertices — an Euler path exists.

THE TECHNIQUE Euler path iff 0 or 2 odd-degree vertices (circuit iff 0)

The demo counts the odd-degree vertices of the graph — exactly 2, so an Euler path exists: live demo

HISTORY & CREDIT Leonhard Euler · 1736 (Königsberg)

“You can always find a route crossing each edge once.” — only with 0 or 2 odd-degree vertices; Königsberg’s four odd vertices made it impossible. cited

the condition · an Euler path needs 0 or 2 odd-degree vertices; a circuit needs 0.
the reason · passing through a vertex uses 2 edges — interior vertices must be even; ends may be odd.
1736 · Euler — the Königsberg bridges (four odd vertices → impossible); graph theory begins.

A walk crossing every edge once — possible exactly when at most two vertices have odd degree. theorem

RECOMMEND FOR I-13 the odd-degree count, on the compiler

On the canonical compiler, the graph has exactly 2 odd-degree vertices — so an Euler path exists:

$ i13 run nw_eulerpath.i13 # count odd-degree vertices RUN OK · 814 step(s) · peak stack 25 · call depth 11 odd_count = 2 euler_ok = 1 -- 0 or 2 odd vertices: an Euler path exists

Recommend as a NULL — a theorem, the founding one. The Euler-path condition is a characterization theorem (exists iff 0 or 2 odd-degree vertices, B39), following from the handshaking lemma (dart 529). i13 confirms the count (2, so a path exists). A criterion the computation obeys, not one it enacts. NULL — the walk that began graph theory in Königsberg.