A topic in the Open Knowledge Graph — a free, open map of 15,290 topics and the order to learn them in.
The Four Color Theorem states that every planar graph is 4-colorable. Despite its simple statement, the only known proofs are computational, relying on case analysis via computer verification. This theorem marks a shift in mathematics toward algorithmic and computer-assisted proofs.
You already know that a planar graph is one that can be drawn in a plane without edge crossings, and that graph coloring assigns colors to vertices so that no two adjacent vertices share a color. The Four Color Theorem asks: how many colors do you ever need to color a planar graph properly? The answer is at most four — no matter how complex the planar graph, four colors always suffice.
The map-coloring version of this question is easier to visualize. Imagine a political map where you want to color countries so that no two neighboring countries share a color. Each country is a region, and the coloring rule says bordering regions must differ. If you convert this to graph theory — make each country a vertex and draw edges between neighboring countries — the result is a planar graph (because countries are regions on a flat map, and their borders don't cross). The Four Color Theorem then tells you that four colors are enough for any such map. Cartographers discovered empirically long before 1879 that four colors appeared sufficient; proving it took nearly a century.
Three colors are not always enough — you can construct planar graphs requiring four — but five colors are more than sufficient, and proving the Five Color Theorem is a clean, elegant exercise using a technique called Kempe chains. The jump from five to four is where the difficulty lies. After failed attempts at clean proofs (including a "proof" in 1879 that stood for 11 years before a flaw was found), Appel and Haken proved the theorem in 1976 by reducing the problem to checking roughly 1,900 specific graph configurations by computer. This was the first major theorem whose proof relied essentially on computer assistance, and it sparked genuine debate among mathematicians about what counts as a proof.
The theorem's significance extends beyond maps and colorings. It reveals that planarity is a very strong constraint on graph structure — planar graphs are sparse enough and well-behaved enough that four colors are always sufficient regardless of complexity. It also opened the door to computer-assisted mathematics: problems too vast for human case analysis could now be tackled algorithmically. A shorter, more conceptual proof remains an open goal, and the search has deepened the theory of planar graphs considerably.