**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 .
- they cannot cross at an edge (planarity) and
- they cannot cross at a vertex (because of the coloring).

## We now have a contradiction, because... (π€ click the toggle to reveal the spoiler!)

...these paths MUST cross, but -

This is a contradiction.

Β

Β

Ta-da! π

Β

Β

Β