Five Color Theorem

The four color theorem states that every vertex of a planar graph can be colored with one of 4 colors so that no two adjacent vertices share a color. Its proof is very long and complicated. The weaker five color theorem, however, has a concise and elegant proof, good enough to appear in "Proofs From The Book." Our task is to write a program that assigns one of the numbers 1, 2, 3, 4, 5 to each vertex of a graph. The code must be concise and elegant enough to appear in "Codes From The Book."

Here is the proof of the five color theorem. In 1879 Alfred Kempe actually proved the four color theorem this way, but 11 years later John Percy Heawood found a fatal flaw in that proof. The proof we will look at is the five color theorem proof that Heawood completed by fixing Kempe's proof. Unfortunately, this is not the proof that appears in "Proofs From The Book." There are several reasons we present this proof instead.

1. It is the best-known proof of the five color theorem. In fact, the Wikipedia article "Five color theorem" also gives this proof.
2. The proof in "Proofs From The Book" uses the concept of list coloring. Using it would require defining list coloring, and there is more preparation than we judged suitable for an introduction to readers who know no graph theory at all.
3. The proof in "Proofs From The Book" is very concise and elegant, but hard to turn into code. There are many steps that are complicated to implement, such as triangulating, finding the cycle adjacent to the outer face, and finding a chord and splitting the graph. As always, what is mathematically elegant and what is algorithmically elegant can differ. The proof we present is concise and elegant enough, and its implementation is intuitive.
4. We thought this proof was in "Proofs From The Book," but after finishing the write-up we found it was not.

In the theorems below we assume every graph is simple. That is, there is no edge whose endpoints are the same, and no two edges connect the same pair of vertices. First we introduce Euler's formula for planar graphs.

Theorem 1. For a connected planar graph with V vertices, E edges, and F faces, V-E+F = 2.

We count the infinitely large face, like the shaded one in the figure below.

Proof. [TODO: to be added] ■

Now for a few lemmas.

Lemma 2. For the degree deg(v) of a vertex v, ∑deg(v) = 2E.

Proof. Let N be the number of pairs (v, e) of a vertex v and an edge e incident to v. Each v is incident to deg(v) edges, so N = ∑deg(v). Each edge is incident to two vertices, so N = 2E. Combining the two equations gives ∑deg(v) = 2E. ■

Lemma 3. For a planar graph with V > 2, E ≤ 3V - 6.

Proof. Assume the graph is connected. If it is not, we can add edges while keeping the graph planar to make it connected. If F = 1, then E = V-1 ≤ 3V - 6 by Theorem 1.

If F > 1, let N be the number of pairs (e, f) of an edge e and a face f incident to e. Since the graph is simple, each face is incident to at least 3 edges, so N ≥ 3F. Each edge is incident to at most 2 faces, so N ≤ 2E. Combining the two gives 3F ≤ 2E. By Theorem 1, V-E+F = 2, so 3F = 6-3V+3E ≤ 2E. Rearranging gives E ≤ 3V - 6. ■

[TODO: the proof above fails when F=1. Rewrite it]

Lemma 4. Every planar graph has a vertex of degree at most 5.

Proof. If V < 6 this is obvious. If V > 6, define d as the average degree ∑deg(v)/V of the graph's vertices. By Lemma 2, d = 2E/V. By Lemma 3, d ≤ (6V-12)/V < 6. Since the average degree is less than 6, some vertex has degree less than 6. ■

Now we can prove the five color theorem.

Theorem 5. Every vertex of a planar graph G can be colored with one of 5 colors so that no two adjacent vertices are colored the same.

Proof. We use induction on V. If V < 6 this is obvious. By Lemma 4 there is a vertex of degree at most 5. Call it v. Let G-v be the graph obtained by removing v and all edges incident to v from G. By the induction hypothesis, every vertex of G-v can be colored with one of the 5 colors.

Now we carry the colors of the vertices of G-v over to the vertices of G except v, and must decide the color of v. List the vertices adjacent to v clockwise as u1, u2, ..., uk. Here k = deg(v). If k < 5, or if k = 5 and some pair ui, uj share a color, then simply color v with a color not used by its neighbors.

The problem is the case k = 5 where all ui have distinct colors. Here we use the idea of a Kempe chain. Without loss of generality, assume ui is colored with the i-th color for each i. Define Ki,j as the set of all vertices v satisfying the following. Of course ui itself belongs to Ki,j.

"There is a path from ui to v whose every vertex has color i or j. (For convenience, call the i-th color simply i.)"

If K1,3 does not contain u3, swap the colors of all vertices in K1,3: colors that were 1 become 3 and colors that were 3 become 1. Now u1 has color 3, so v can be colored 1.

[TODO: insert a figure here. When will I ever finish drawing all of these...]

If K1,3 contains u3, then since G is planar, K2,4 cannot contain u4. So swap the colors of all vertices in K2,4 and color v with 2. This completes the proof. ■

[TODO: insert a figure here]

[TODO: should we include the Book proof too?]

[TODO: actually, would including only the Book proof be fitting for a joke contest?]

The first line gives the number of vertices N and the number of edges M of the graph. The vertices are numbered with the integers 1 through N, one number each. The next N lines give the coordinates of each vertex, one vertex per line. Starting from line N+2, M lines give the endpoints of each edge, one edge per line. N is an integer from 3 to 100, and M is a positive integer at most 3N-6. Every vertex coordinate is an integer from -1,000 to 1,000.

No two points share a location, there is no edge whose endpoints are the same, and no two edges connect the same pair of vertices.

Print N digits with no spaces. The x-th digit is the number assigned to the x-th vertex. If several valid assignments exist, print any one of them.