Yakk wrote:Apparently, the five colour theorem proof is far easier than the four colour theorem proof. If I remember rightly, it reduces to taking something like the above (where the colours don't allow for another in the middle) and proving that there is a method to move colours around to free up a colour.
Pretty much. Here's a quick picture-free argument.
First, It is a trivial consequence of Euler's Formula that all planar graphs can be six-colored. Assume that there is some planar graph that cannot be five-colored, so that we may choose such a graph G that has a minimum number of vertices. G has some vertex v with degree of five or less. By minimality, G-v can be five-colored, so choose such a coloring and apply it to G. Since G cannot be five-colored, it must be that v has exactly five neighbors, and that they each have a different color***. Arbitrarily picking one of those neighbors and proceeding "clockwise" around v in our planar embedding, call those five colors 1, 2, 3, 4, and 5 and their corresponding vertices u1 through u5.
Now, consider the subgraph of G of all vertices with colors 1 and 3. If u1 and u3 are not in the same component, then we can show a five-coloring of the graph by switching all of the colors 1 and 3 in the component of the subgraph that contains u1, and then assigning color 1 to v. However, we have assumed that this is impossible, so u1 and u3 are connected in this subgraph, and therefore there is a path joining u1 to u3 that consists only of vertices labeled 1 and 3. Adding v to this path forms a cycle C in G; u2 is in the interior of this cycle and u4 is in the exterior. Now, consider the subgraph of all vertices with colors 2 and 4. Here, we know that u2 and u4 cannot be in the same component, because they are separated by a cycle which contains none of the vertices in the subgraph. Therefore, we may fulfill the program illustrated earlier in this paragraph to construct a five-coloring for G. Since we have assumed that to be impossible, our assumption that there is a planar graph that cannot be five-colored must have been erroneous. QED
Note: Novices look at this proof, observe that we didn't use u5 at all, and rush to conclude that this must be easily adaptable to a two-paragraph proof of 4CT. Such a proof is ungrounded because of the line that I marked ***. All we can say is that v has either four neighbors or five, and if there are five then the two neighbors that receive the same color are either "adjacent" (in the sense that they could be assigned vertices u1 and u2) or not (being, say, u1 and u3). Kempe's original proof of 4CT (which is around six paragraphs long) assumes that you can make this sort of "Kempe chain" argument for each of these three subcases, but the final case is sufficiently troublesome that the argument turns out to not work.