Five Color Theorem
From ProofWiki
[edit] Theorem
Any planar graph
can be assigned a proper vertex
-coloring such that
.
[edit] 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
edges, and each edge bounds at most
faces, so
.
We first suppose that every vertex of
is incident on
edges or more.
|
|
| By the Euler Polyhedron Formula | |||
|
|
| ||||
|
|
| ||||
|
|
| ||||
|
|
|
However, if every vertex has degree greater than
as we supposed,
, which is a contradiction.
Therefore,
has at least one vertex with at most
edges, which we will call
.
Remove that vertex
from
to create another graph,
.
By the induction hypothesis,
is five-colorable.
If all five colors were not connected to
, then we can give
the missing color and thus five-color
.
If all five colors were connected to
, we examine the five vertices
was adjacent to, and call them
,
,
,
, and
(in order around
).
We color
,
,
,
, and
, 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
of
consisting only of vertices colored
and
and the edges that connect vertices of color
to vertices of color
.
If there is no walk between
and
in
, then we simply switch colors
and
in the portion of
connected to
.
Thus,
is no longer adjacent to a vertex of color
, so we can color it
.
If there is a walk between
and
in
, then we proceed to form
in the same manner.
However, since
is planar and there is a circuit in
that consists of the walk from
to
,
, and the edges
and
, clearly
cannot be connected to
within
.
Thus, we can switch colors
and
in the portion of
connected to
.
Thus,
is no longer adjacent to a vertex of color
, so we can color it
.
This graph illustrates the case in which the walk from
to
can be completed.
,
,
,
, and
.
The dotted lines represent edges and vertices that might exist, as this is simply a fairly minimal example graph that matches the conditions.
[edit] 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.

