Four Color Theorem — Definition, Formula & Examples
The Four Color Theorem is the proven result that any map drawn on a flat surface can be colored using at most four colors, with the rule that no two regions sharing a border receive the same color.
For any planar graph , the chromatic number satisfies . Equivalently, every planar graph admits a proper vertex coloring using no more than four colors, where no two adjacent vertices share the same color.
How It Works
Think of any map — countries, states, or arbitrary regions. You want to color each region so that neighbors (regions sharing a boundary line, not just a single point) get different colors. The theorem guarantees you never need a fifth color, no matter how complicated the map is. To apply it, start coloring regions one at a time, choosing from four colors and avoiding conflicts with already-colored neighbors. If you get stuck, you can always rearrange previous color choices to make it work with just four.
Example
Problem: A simple map has 5 regions: A borders B and C; B borders A, C, and D; C borders A, B, D, and E; D borders B, C, and E; E borders C and D. Color this map using at most 4 colors.
Step 1: Assign color 1 (red) to region A.
Step 2: Region B borders A (red), so assign color 2 (blue) to B.
Step 3: Region C borders A (red) and B (blue), so assign color 3 (green) to C.
Step 4: Region D borders B (blue) and C (green), so assign color 1 (red) to D — reusing red is fine since D does not border A.
Step 5: Region E borders C (green) and D (red), so assign color 2 (blue) to E.
Answer: A = red, B = blue, C = green, D = red, E = blue. Only 3 colors were needed here, well within the 4-color guarantee.
Why It Matters
The Four Color Theorem was the first major theorem proved with substantial computer assistance (1976), sparking debate about what counts as a mathematical proof. Graph coloring techniques built on this idea are used in scheduling problems, register allocation in compilers, and wireless frequency assignment where nearby transmitters must use different channels.
Common Mistakes
Mistake: Assuming two regions that touch at a single point count as "adjacent" and need different colors.
Correction: Only regions sharing a common boundary segment (not just a point) are considered adjacent. Think of four squares meeting at a corner — diagonal squares can share a color.