Five Color Theorem

== Theorem ==
A planar graph $G$ can be assigned a proper vertex $k$-coloring such that $k \le 5$.
== Proof ==
The proof proceeds by the Principle of Mathematical Induction on the number of vertices.
For all $n \in \N_{> 0}$, let $\map P n$ be the proposition:
:$G_n$ can be assigned a proper vertex $k$-coloring such that $k \le 5$.
=== Basis for the Induction ===
$\map P r$ is trivially true for $1 \le r \le 5$, as there are no more than $5$ vertices to be colored.
This is our basis for the induction.
=== Induction Hypothesis ===
Now we need to show that, if $\map P r$ is true, where $r \ge 5$, then it logically follows that $\map P {r + 1}$ is true.
So this is our induction hypothesis:
:$G_r$ can be assigned a proper vertex $k$-coloring such that $k \le 5$.
Then we need to show:
:$G_{r + 1}$ can be assigned a proper vertex $k$-coloring such that $k \le 5$.
=== Induction Step ===
This is our induction step:
According to the Minimum Degree Bound for Simple Planar Graph, $G_{r + 1}$ has at least one vertex with at most $5$ edges.
:Let this vertex be labeled $x$. 
Remove vertex $x$ from $G_{r + 1}$ to create another graph, $G'_r$.
By the induction hypothesis, $G'_r$ is five-colorable.
Suppose all five colors were not connected to $x$.
Then we can give $x$ the missing color and thus five-color $G_{r + 1}$.
Suppose all five colors are connected to $x$.
Then examine the five vertices $x$ was adjacent to.
Call them $y_1, y_2, y_3, y_4$ and $y_5$ in clockwise order around $x$.
Let $y_1, y_2, y_3, y_4$ and $y_5$ be colored respectively by colors $c_1, c_2, c_3, c_4$ and $c_5$.
Let us denote $H_{i, j}$ a subgraph of $G'_r$ induced by the vertices colored with $c_i$ and $c_j$. 
Consider $H_{1, 3}$. 
Suppose there exists no path between $y_1$ and $y_3$ in $H_{1, 3}$. 
Thus, $H_{1, 3}$ is disconnected into two components.
We can, then, interchange the colors $c_1$ and $c_3$ in the component that is connected to $y_1$.
Thus $x$ is no longer adjacent to a vertex of color $c_1$, so $x$ can be colored $c_1$.
Suppose there exists a path between $y_1$ and $y_3$ in $H_{1, 3}$.
Including the vertex $x$ in this path we get a circuit $C$.
Since we indexed the vertices $y_1, y_2, y_3, y_4$ and $y_5$ clockwise, exactly one of the vertices $y_2$ and $y_4$ is inside $C$.
Hence, $y_2$ and $y_4$ are in different connected components of $H_{2, 4}$
Then we can switch colors $c_2$ and $c_4$ in the component of $H_{2, 4}$ that is connected to $y_2$.
Now $x$ is no longer adjacent to a vertex of color $c_2$, so we can color it $c_2$.
:
This graph illustrates the case in which the path from $y_1$ to $y_3$ can be completed.
:$\text{Blue} = c_1, \text{Yellow} = c_2, \text{Red} = c_3, \text{Green} = c_4, \text{Turquoise} = c_5$.
The dotted lines represent edges and vertices that might exist, as this is simply a fairly minimal example graph that matches the conditions.
So $\map P r \implies \map P {r + 1}$ and the result follows by the Principle of Mathematical Induction.
Therefore:
:For all $n \in \N_{>0}$, $G_n$ can be assigned a proper vertex $k$-coloring such that $k \le 5$.
== Also known as ==
This theorem is also known as Heawood’s Theorem, for , although The Five-Color Theorem is more widely used.
The British English spelling of this proof is five colour theorem.
== Also see ==
* The proof gives a simple (recursive) algorithm for $5$-coloring a planar graph, the so-called Heawood's Algorithm.
== Historical Note ==
Category:Named Theorems
Category:Graph Theory
Category:5