We know that the graphs $K_5$ and $K_{3,3}$ are not planar.
The complete graph $K_5$ means that all 5 vertices are adjacent, thus requiring 5 different colors to allow coloring without two adjacent vertices having the same color.
The same applies to $K_{3,3}$ (a bipartite 3 by 3 graph), where each vertex is connected to not more than 3 other vertices.
Both $K_5$ and $K_{3,3}$ can be made planar by just taking away one single edge in each. Thus, 4 colors suffice to color the modified $K_5$, while the K3,3 is even 2-colorable.
Thus, it looks like the Four-Color Theorem would be proved by Kuratowski's theorem – no planar graph contains a $K_5$ nor a $K_{3,3}$.
Then, the biggest group of fully connected vertices would be 4 as in the modified $K_5$.
Could anyone explain why the above-mentioned condition is only necessary but not sufficient ?
Best Answer
The existence of a $K_5$ would be a local obstruction to four-colourability. There could also be global obstructions, which need to be eliminated too.
The proof shows that all potential obstructions are essentially local, and then systematically shows that they are not obstructions. The configurations which have to be considered are rather larger than $K_5$.
Note that a single region surrounded by a ring of an odd number of others (say seven) requires four colours. But this configuration does not contain four regions which are mutually adjacent ($K_4$). So local obstructions to three-colourability are more complex than we might first think.
Of course, since the four colour theorem is true, the absence of $K_5$ or $K_{3,3}$ does imply that the graph is planar and four colourable. The first of these is easily shown. No-one knows an easy way of proving the second