Can you trace a network crossing every EDGE exactly once, without lifting your pen? Euler cracked it in 1736 (the Bridges of Königsberg) with a shockingly simple rule: it’s possible only if ZERO or exactly TWO nodes have an odd number of connections. Zero odd → you end where you began; two odd → you start at one and end at the other. That single count founded graph theory. Slide to check the degrees and trace the path.
An Eulerian trail uses every EDGE of a connected graph exactly once. Euler’s theorem (1736, the Seven Bridges of Königsberg — the birth of graph theory): such a trail exists iff the graph is connected and has ZERO odd-degree vertices (then it’s a closed circuit, start=end) or EXACTLY TWO (an open path between them); any other odd count makes it impossible, because each interior visit to a vertex uses two edges (in+out) so odd endpoints must be trail ends. Hierholzer’s algorithm then constructs it in O(E). It underlies DNA fragment assembly (de Bruijn graphs), route/mail-carrier problems, and one-stroke drawings. A fail-loud self-check throws unless the odd-degree count correctly predicts a path/circuit/none. ◆ real graph algorithms, node-verified.
The parity rule assumes the graph is CONNECTED (isolated pieces break it); it decides EXISTENCE — Hierholzer builds the actual trail. Contrast the [[the-dijkstra|Hamiltonian]] path (every VERTEX once), which is NP-hard. The degree-parity theorem is exact.