Proving the Four-Color Map Theorem

When I was young, I proved the famous 4-color map theorem! Or thought I did, for just a brief moment. It was a few days before I looked at it clearly enough to spot the flaw, but I knew there had to be one. Let me give that simple proof here. See if you can spot the flaw! Remember that a planar graph has Vertices, Edges and Faces, and it's the Vertices that we are coloring.

Lemma: Any finite planar graph will have a vertex of valence five or less, i.e. a vertex connected via edges to five or fewer other vertices.

Proof: Recall Euler's V + F = E + 2. Suppose the average valence is k. Then the number of Edges is E = kV/2. (Divide by 2 since each Edge has two Vertices.) Similarly E = mF/2 where m is the average number of edges per face. Combine these three equations to solve for V in terms of m and k and get V = 4m / (2m + 2k - km). The denominator must be positive; so k < 2m/(m-2). But we know m ≥ 3 since no faces have fewer edges than a triangle. These two inequalities imply that k < 6. The average valence is less than 6; all we needed was the weaker result that some valence is less than 6.
 

Now suppose that G is the smallest finite planar graph that cannot be 4-colored. We will remove a vertex (V) of valence five or less from that graph. The resultant graph {G-V} can be 4-colored, since G was minimal. We will manipulate that 4-coloring until it can be extended to the full graph, with V added back in. Once we've demonstrated a 4-coloring of G, we've proved the 4-color map theorem by contradiction. In the first figure, we show part of the graph {G-V}. We show where V was removed, leaving behind a pentagonal face. We show a 4-coloring of that face. This is the only case we need consider. If V had valence 4, or left behind a 3-colored pentagon, the proof would be much simpler than this case we do consider. The plan is to manipulate the colors until the pentagon uses only three colors instead of four. If we can do that, V is restored, colored with the fourth unused color, and the Four-Color Map proof is complete! For example, we could change the pentagon's green vertex to yellow. To maintain a valid 4-coloring for {G-V} we would change all if its adjacent yellow vertices to green, all their adjacent green vertices to yellow, and so on. The whole yellow-green subgraph connected to the first green vertex undergoes the Green <--> Yellow transformation. In the diagram we show that the pentagon's yellow vertex is part of that subgraph. It must be so! -- otherwise G could be 4-colored without further ado. So let's not change that Green to Yellow after all; let's look for something else.

 

A similar attempt can be made to recolor the green vertex blue. And again it must fail, for the same reason. In the second diagram we show that the pentagon's green and blue vertices are in the same connected green-blue subgraph. Foiled again! But not so fast ... Look at the red vertex at the top of our pentagon We can change its color to yellow (and its adjacent yellows to reds, and their adjacent reds to yellows and so on) without fear of encountering the yellow vertex at the pentagon's lower left. The Green-Blue chain, which we've proven must exist, isolates the Yellow-Red subgraph we're working on. This is a definitional property of planar graph: a yellow-red edge cannot pass a blue-green fence without tunnelling under it, or leaping over it; these are forbidden in planar graphs. To avoid cluttering the diagram, we don't show it, but the Red vertex in the lower right of the pentagon can be similarly changed to Blue. And again the remainder of the pentagon is unaffected: the red-blue subgraph cannot tunnel through the green-yellow fence we've proven to exist. So, we change one of the pentagon's red vertices to yellow, and the other red vertex to blue, without affecting the rest of the pentagon. The color Red is now available! Restore the vertex V with its five edges; color it Red; G is now 4-colored; the 4-Color Map Theorem is true. Q.E.D. !!

 

This proof is fallacious! I do know where the fallacy is but I'm tired of typing for now. As an experiment to see how many people enjoy my pages, please feel free to e-mail me if you want to tell me what the fallacy is!