Theorem

For every planar graph, there exists a coloring of its vertices usingat most 5 colors such that no two adjacent vertices have the same color.

Lemma: degree 5 vertex

To show that every planar graph has at least 1 vertex of degree $\leq 5$, we assume euler's formula, that given $F$ faces, $V$ vertices, and $E$ edges of a planar graph, that $$F + V = E + 2.$$

We assume for contradiction, there exists a planar graph $G = (F, V, E)$ with all vertices of degree $\geq 6$. Then let us consider the size of this set:

$$VE = \{(v,e) : v \in V, e \in E, v \text{ is adjacent to } e\}$$

Every edge will be in there twice, so $$|VE| = 2|E|.$$ Also, we know that all vertices have at least 6 edges, so $$|VE| \geq 6|V|.$$ Thus, $$2|E| \geq 6|V| \implies \frac{1}{3}|E| \geq |V|.$$

Next, consider the set:

$$FE = \{(f,e) : e \in E, f \in F, f \text{ is adjacent to } e\}$$

Every edge can see 2 faces, so $$|FE| = 2|E|,$$ and every face has at least 3 edges, so $$|FE| \geq 3|F|.$$ Putting this together, $$2|E| \geq 3|F| \implies \frac{2}{3}|E| \geq |F|.$$

Now, we apply Euler's formula to get:

$$2 = F + V - E$$$$\leq \frac{2}{3}|E| + \frac{1}{3}|E| - |E|$$$$= 0.$$

Thus, $2 \leq 0$, a contradiction. This concludes the proof.

—

Proof

Now for the real proof. This proof is by induction on the number of vertices ina planar graph:

Base case: $|V|=1$, it is clear that this is 5-colorable with just 1 color.

Inductive step: We assume that all planar graphs with $|V|-1$ vertices are 5colorable. We know from the lemma that there exists at least one vertex $w$ ofdegree 5 or less. We know that if it has less degree less than 5 that we instantly win because ifwe remove that vertex, it is 5 colorable (from our inductive hypothesis). Andbecause $w$ has degree less than 5 it can be colored by a color that isn't inits neighbors. Thus, we can assume $w$ has 5 neighbors.

Now, because $w$ has 5 neighbors, if any two of them have the same color, then wecan color $w$ the color that is missing, so we can assume that $w$ has degree atleast 5.

To recap what we know so far: all planar graphs have at least one vertex with less thandegree 5. The worst-case scenario for our proof is when it is exactly 5, and allof the neighbors have different colors. In all other cases, we win.

Now, we label the neighbors $v_1$ through $v_5$ based on their colors. We lookat the largest subgraph that connects to vertex $1$ which only contains $1$ and$3$ colored vertices (it can have other colors hanging off of it). Now, if itdoesn't contain $v_3$ then we can flip the color of each of the vertices of thesubgraph (i.e. every $1$ colored vertex becomes a $3$ colored vertex). And thenwe can just color $w$ $1$ because it will have 2 vertices of color $3$ adjacentto it and no vertices of color $1$ now.

Thus, we can assume that there is an unbroken path from $v_1$ to $v_3$ whichcontains only $1$ and $3$ colored vertices. Now, we can apply the same exactlogic to the colors $2$ and $4$. Thus, we only care about the case when thereis an unbroken path from $v_2$ to $v_4$, as otherwise we can just flip the colorsfo the subgraph coming from $v_2$ to recolor $w$ with color $2$. However, therecan't be both an unbroken path from $v_1$ to $v_3$ using only $1$ and $3$colored vertices, and an unbroken path from $v_2$ to $v_4$ using only $2$ and$4$ colored vertices. The paths have to cross because they are paths on a plane.This that case leads to a contradiction, so any planar graph must've fallen intoone of the cases that was 5 colorable. Thus, every planar graph is 5 colorable. This concludes the proof.

—