📐 Five Color Theorem

Every planar graph is 5-colorable.

Proof: Induction on $n$. By the edge bound, some vertex $v$ has degree $\\leq 5$. Remove $v$, 5-color the rest by induction. If $d(v) < 5$ or two neighbors share a color, color $v$ with an available color. Otherwise, $v$ has 5 differently-colored neighbors. Consider a Kempe chain argument: swap colors a...

From: Introduction to Graph Theory

Learn more: https://west-graphs-deploy.vercel.app/#/section/19

Explore all courses: https://mathacademy-cyan.vercel.app