Coloring Planar Graphs

Graph Theory · Axiom Academy

Exploring the fundamental theorems of graph coloring, from the trivial six-color theorem to the famous four-color theorem 1. The Six-Color Theorem (Trivial from Euler) Every planar graph can be colored with at most 6 colors . This follows almost immediately from Euler's formula. Watch as we demonstrate the proof technique using a small planar graph: 2. The Five-Color Theorem (Heawood's Proof) Every planar graph can be colored with at most 5 colors . This theorem was proved by Percy Heawood in 1890, with a relatively straightforward inductive argument. The animation shows the Kempe chain technique when v has 5 neighbors: Every planar graph can be colored with at most 4 colors . This is one of the most famous theorems in mathematics, conjectured in 1852 and finally proved in 1976 by Appel and Haken using computer assistance. Here's an example showing that 4 colors suffice for a complex planar graph: 4. Heawood's Formula for Surfaces What about graphs drawn on other surfaces, like the torus or Möbius strip? Heawood discovered a beautiful formula that gives the chromatic number for graphs on most surfaces. The animation shows how graphs on different surfaces require different numbers of colors: 5. Applications to Map Coloring The original motivation for the four-color theorem was map coloring: can any map be colored with just four colors so that no adjacent regions share a color? Watch the conversion from a map to a planar graph:

This is the written version of the interactive lesson above. See the full Graph Theory course.