In 1736 Euler was handed a walking puzzle about the seven bridges of Königsberg — and answered it by throwing the map away. Keep only what touches what, and a river town becomes four dots and seven lines. That single act of forgetting geography is the birth of graph theory. Three tabs below let you walk the bridges, colour a graph down to its chromatic number, and four-colour a map that seems to demand five. Everything is computed live — the counters read the graph, they are not captions.
Model each land mass as a vertex and each bridge as an edge. The degree of a vertex is the number of edges meeting it. A walk that uses every edge exactly once is an Euler path (an Euler circuit if it also returns home).
Every time the walk visits an interior vertex it arrives on one edge and leaves on another — edges get consumed two at a time. So a vertex you merely pass through must have even degree. The only vertices allowed to be odd are the two endpoints of the walk (or none, if start = finish).
Königsberg's degrees are 5, 3, 3, 3 — four odd vertices. Since a path permits at most two, no route can cross all seven bridges once. That is Euler's 1736 result, usually called the first theorem of graph theory.
A companion fact — the Handshake Lemma — says the degrees always sum to twice the number of edges, so the count of odd-degree vertices is always even. That's why fixing the puzzle takes a single new bridge: adding one edge flips the parity of exactly its two endpoints, turning four odd vertices into two.
A proper colouring assigns each vertex a colour so that adjacent vertices differ. The chromatic number χ(G) is the fewest colours that admit a proper colouring. A single triangle already needs 3; more generally any odd cycle needs 3, and a clique of n mutually-joined vertices needs n.
The graph here is the octahedron, K2,2,2: six vertices, the only non-edges being the three "antipodal" pairs. Colour each antipodal pair alike and three colours cover everything — but it's packed with triangles, so two never can. Hence χ = 3.
Finding χ in general is NP-hard — there's no known fast recipe for large graphs — which is exactly why it models so many real bottlenecks: exam timetabling (exams that share a student are adjacent), radio-frequency assignment (nearby transmitters are adjacent), register allocation in compilers (variables live at once are adjacent), and Sudoku (a 9-colouring of a 81-vertex graph).
Greedy colouring — take vertices in some order, give each the lowest colour not used by its neighbours — is fast and never uses more than Δ+1 colours (Δ = max degree). It isn't always optimal, but it's the workhorse the auto-colour button runs.
Turn a map into a graph: one vertex per region, an edge whenever two regions share a border (a single touching point doesn't count). Colouring the map is then exactly proper vertex-colouring of this planar graph. This map's graph is the wheel W₅ — a hub joined to a 5-cycle rim — whose chromatic number is 4.
Why can't a map ever need more? Because planar graphs are sparse: they can't contain K₅ (five mutually-bordering regions) or K₃,₃. Getting from "sparse" to "four is enough" is famously hard — five colours is an easy afternoon's proof, four resisted for over a century.
Conjectured by Francis Guthrie in 1852, the Four-Colour Theorem was finally proved by Appel and Haken in 1976 — the first major theorem whose proof required a computer. They reduced every possible map to 1,936 unavoidable configurations and had a machine check each one could be four-coloured, hundreds of hours of computation no human could redo by hand.
That sparked a lasting debate: if no person can verify every step, is it really a proof? Modern formal-verification systems (Coq, 2005) have since machine-checked the machine-check, and the result stands. It remains the emblem of a new kind of mathematics — true, but only readable by computers.