The Königsberg Bridge Problem

Euler, 1736 — The birth of graph theory

Geographic Layout
A B C D North Bank South Bank Island Pregel River
Euler's Abstraction
2 edges 2 edges A C B D deg = 3 deg = 3 deg = 5 deg = 3
Vertex Represents Degree Parity
A North bank 3 Odd
B South bank 3 Odd
C Island 5 Odd
D East land 3 Odd
All four vertices have odd degree. Euler proved that an Eulerian circuit requires all vertices to have even degree, and an Eulerian path requires exactly two odd-degree vertices. With four odd vertices, neither is possible — the walk cannot be completed.