# Five Color Theorem

Status
Zombie
Title
Test
Date
Excerpt
Published
Sep 9, 2021
Tags
Feature on homepage
Theorem. A planar graph can be colored with at most five colors.
Proof sketch. A planar graph must have a vertex, say , of degree at most five (why?). Testing...
Let be a 5-coloring of the graph (by the π© induction hypothesis).

If has:
• [Case 1] less than five neighbors in , or
• [Case 2] five neighbors that have a repeated color amongst them
then: (π€ click toggle to find out what happens.)
can be easily extended to a coloring of by using the βmissing colorβ on the vertex .
Β

Β
Otherwise, has five neighbors, all colored with distinct colors. Assume, WLOG, that the vertices in the neighborhood of , denoted appear clockwise in a fixed planar drawing of the graph . Suppose we have:
red, blue, green, purple, orange
Β

Β
Consider the subgraphs and consisting of only the red and green; and the blue and purple vertices of , respectively (with respect to the coloring ).
We now have the following.
• If and do not belong to the same connected component of , then swap the colors red and green in the connected component containing to go to Case 2.
• If and do not belong to the same connected component of , then swap the colors red and green in the connected component containing to go to Case 2.
• If neither of the above hold, then:
• there is a red-green path from to and
• there is a blue-purple path from and .
• We now have a contradiction, because... (π€ click the toggle to reveal the spoiler!)
...these paths MUST cross, but -
• they cannot cross at an edge (planarity) and
• they cannot cross at a vertex (because of the coloring).