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.

Lemma 6  is proven by an examination of the following cases:

A map has a region with 2, 3, or 4 edges.

A map has a region with exactly 5 edges. 

    For the last case a consideration of the "duality" shows that at least two of the regions on the 5 boundary edges  have no common border.[In essence this also uses the Euler formula in demonstrating that the complete graph on five vertices cannot lie in the plane.]


The Four Color Theorem is not as easy!