Five Color Theorem

Theorem

Any planar graph $G$ can be assigned a proper vertex $k$-coloring such that $k \le 5$.

Proof

It is obvious the theorem is true for a graph with only one vertex. We will induct on the number of vertices.

Each face of a planar graph is obviously bounded by at least $3$ edges, and each edge bounds at most $2$ faces, so $\dfrac 2 3 e \ge f$.

We first suppose that every vertex of $G$ is incident on $6$ edges or more.

	\(\displaystyle \)	\(\displaystyle 2\)	\(=\)	\(\displaystyle v - e + f\)	\(\displaystyle \)	By the Euler Polyhedron Formula
	\(\displaystyle \)	\(\displaystyle 2\)	\(\leq\)	\(\displaystyle v - e + \frac2 3 e\)	\(\displaystyle \)
	\(\displaystyle \)	\(\displaystyle e\)	\(\leq\)	\(\displaystyle 3v - 6\)	\(\displaystyle \)
	\(\displaystyle \)	\(\displaystyle 2e\)	\(\leq\)	\(\displaystyle 6v - 12\)	\(\displaystyle \)
	\(\displaystyle \)	\(\displaystyle \sum \text{degrees}\)	\(\leq\)	\(\displaystyle 6v - 12\)	\(\displaystyle \)

However, if every vertex has degree greater than $5$ as we supposed, $\sum \text{degrees} \ge 6v$, which is a contradiction.

Therefore, $G$ has at least one vertex with at most $5$ edges, which we will call $x$.

Remove that vertex $x$ from $G$ to create another graph, $G'$.

By the induction hypothesis, $G'$ is five-colorable.

If all five colors were not connected to $x$, then we can give $x$ the missing color and thus five-color $G$.

If all five colors were connected to $x$, we examine the five vertices $x$ was adjacent to, and call them $y_1, y_2, y_3, y_4$ and $y_5$ (in order around $x$).

We color $1, 2, 3, 4$ and $5$ respectively (note that "color" is just a way of labeling the vertices of a graph - it does not actually mean you take crayons and color the graph).

We now consider the subgraph $G_{1,3}$ of $G'$ consisting only of vertices colored $1$ and $3$ and the edges that connect vertices of color $1$ to vertices of color $3$.

If there is no walk between $y_1$ and $y_3$ in $G_{1,3}$, then we simply switch colors $1$ and $3$ in the portion of $G_{1,3}$ connected to $y_1$.

Thus, $x$ is no longer adjacent to a vertex of color $1$, so we can color it $1$.

If there is a walk between $y_1$ and $y_3$ in $G_{1,3}$, then we proceed to form $G_{2,4}$ in the same manner.

However, since $G$ is planar and there is a circuit in $G$ that consists of the walk from $y_1$ to $y_3$, $x$, and the edges $xy_1$ and $xy_3$, clearly $y_2$ cannot be connected to $y_4$ within $G_{2,4}$.

Thus, we can switch colors $2$ and $4$ in the portion of $G_{2,4}$ connected to $y_2$.

Thus, $x$ is no longer adjacent to a vertex of color $2$, so we can color it $2$.

This graph illustrates the case in which the walk from $y_1$ to $y_3$ can be completed.

$\text{Blue} = 1, \text{Yellow} = 2, \text{Red} = 3, \text{Green} = 4, \text{Turquoise} = 5$

The dotted lines represent edges and vertices that might exist, as this is simply a fairly minimal example graph that matches the conditions.

Notes

This is not the strongest result possible. It was shown in 1976 by Kenneth Appel and Wolfgang Haken that four colors suffice. Their proof relies heavily on computers and for the moment is not to be found on ProofWiki.