Color Problems
Outline of the Five Color Theorem Proof
(See Stein, Mathematics: A Man Made Universe or Kinsey and Moore, Symmetry, Shape and Space.)
Theorem: Any map on the sphere (or the plane) can
be colored with five or fewer colors.
Definition: A map is called regular if
every vertex has degree 3.
"Lemma 4": If we can
color every regular map on the sphere with five or fewer colors then
we can color any map on the sphere with five or fewer colors. Proof.
"Lemma 5": A regular map on the
sphere has at least one region with 5 or fewer edges.
Proof: We can count the edges with the vertices, and since there are exactly 3 edges at every vertex we have
3V =2E or V = 2/3 E (*).
But since V+R=E+2 we have R-2= E-V,
and by the equality (*) we have
E - 2/3E = E -V = R -2,
so 1/3E = R - 2.
Now we suppose all regions
have 6 or more edges.
Then 6R ≤ 2E , R ≤ 1/3E .
But then
R ≤ 1/3E = R-2 or R ≤ R-2 which is absurd.
End of proof !
[See also Kinsey amd Moore for a treatment for coloring on any surface.]
"Lemma 6": Any regular map covering the sphere
(or the plane) can be colored with five or fewer colors.
The Four Color Theorem is not as easy!