The Four Color Theorem

The four color theorem states that no more than four colors are required to color the countries of a map so that no two adjacent countries share the same color. To gain an intuition for why this is true, lets try to construct a counterexample

                              

In the left picture we have four countries Red, Blue, Yellow, and Black. We must add the fifth country Green such that all countries touch all other countries. However, we notice that if Green is adjacent to Red, Blue and Yellow, then no matter how we draw it, it encloses a country thereby disconnecting it from Black. An example is shown in the picture on the right where Yellow becomes disconnected from Black (and so you can color them the same color). This seems like it would be an easy theorem to prove using some sort of topological argument, however the only known proofs rely on the aid of a computer. The Supreme Fascist remains unforthcoming.


If you construct a graph by turning each face into a vertex you can rephrase the four color theorem as a statement of vertex colorings of planar graphs. For a graph to be 4-colorable, it is certainly necessary that it not contain a $K_5$ subgraph. But is this condition sufficient? The answer is no, and here is a counterexample

This graph has a chromatic number of 5 but it does not have a $K_5$ subgraph. It also does not contain a subdivision of $K_5$, so it also serves as a counterexample to Hajós' conjecture (first disproved by Catlin in 1979). On the other hand, by contracting both red--pink edges we find that $K_5$ is a minor of this graph, so Hadwiger's conjecture still stands.

_________________________________________________________________________________