Five Color Theorem

From ProofWiki

[edit] Theorem

Any planar graph can be assigned a proper vertex k-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 3 edges, and each edge bounds at most 2 faces, so .

We first suppose that every vertex of G is incident on 6 edges or more.

	2	=	v − e + f		By the Euler Polyhedron Formula
	2
	e		3v − 6
	2e		6v − 12
			6v − 12

However, if every vertex has degree greater than 5 as we supposed, , which is a contradiction.

Therefore, G has at least one vertex with at most 5 edges, which we will call x.

Remove that vertex x from G to create another graph, G'.

By the induction hypothesis, G' is five-colorable.

If all five colors were not connected to x, then we can give x the missing color and thus five-color G.

If all five colors were connected to x, we examine the five vertices x was adjacent to, and call them y₁, y₂, y₃, y₄, and y₅ (in order around x).

We color 1, 2, 3, 4, and 5, 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 G_1,3 of G' consisting only of vertices colored 1 and 3 and the edges that connect vertices of color 1 to vertices of color 3.

If there is no walk between y₁ and y₃ in G_1,3, then we simply switch colors 1 and 3 in the portion of G_1,3 connected to y₁.

Thus, x is no longer adjacent to a vertex of color 1, so we can color it 1.

If there is a walk between y₁ and y₃ in G_1,3, then we proceed to form G_2,4 in the same manner.

However, since G is planar and there is a circuit in G that consists of the walk from y₁ to y₃, x, and the edges xy₁ and xy₃, clearly y₂ cannot be connected to y₄ within G_2,4.

Thus, we can switch colors 2 and 4 in the portion of G_2,4 connected to y₂.

Thus, x is no longer adjacent to a vertex of color 2, so we can color it 2.

This graph illustrates the case in which the walk from y₁ to y₃ can be completed.

Blue = 1, Yellow = 2, Red = 3, Green = 4, and Turquoise = 5.

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.