4
$\begingroup$

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 ?

$\endgroup$
6
  • 8
    $\begingroup$ Why would a graph be $4$-colorable if it doesn't contain $K_5$ or $K_{3,3}$? $\endgroup$
    – TMM
    Mar 2, 2014 at 13:15
  • 1
    $\begingroup$ To give you an example: this graph is planar and does not contain $K_5$ or $K_{3,3}$. How is it obvious that this graph is $4$-colorable? $\endgroup$
    – TMM
    Mar 2, 2014 at 13:22
  • $\begingroup$ To my understanding, a graph could be split into arbitrary subgraphs with max. 5 or 6 vertices each, and each of them would be 4-colorable, because otherwise there would be a $K_5$ or a $K_{3,3}$ in there. If we take any one vertex of such a subgraph as part of another subgraph (which shares only this one vertex or all but one vertex), this would again be 4-colorable, and this would not interfere with the previous subgraph. And one would be able to extend the subgraphs until the entire graph is represented by the union of all subgraphs. $\endgroup$
    – Arc
    Mar 2, 2014 at 13:44
  • $\begingroup$ There is no guarantee that there are no edges between these subgraphs. If you split a graph into two subgraphs and you color them separately without taking note of edges between these subgraphs, you may run into problems by coloring two connected vertices (in different subgraphs) with the same color. $\endgroup$
    – TMM
    Mar 2, 2014 at 14:19
  • 6
    $\begingroup$ The problem you run into is similar to the following: $C_5$ doesn't contain $K_3$ as a subgraph, but is not $2-$ colorable... $\endgroup$
    – N. S.
    Mar 2, 2014 at 19:39

1 Answer 1

Reset to default
13
$\begingroup$

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

$\endgroup$
3
  • $\begingroup$ Do you have a visualization of a simple example for such a graph ? $\endgroup$
    – Arc
    Mar 2, 2014 at 13:41
  • $\begingroup$ I think you're mistaken when you say the absence of $K_5$ implies that the graph is planar and 4-colorable. For instance, replace all edges in $K_5$ with edge-node-edge. This graph is nonplanar, and it's bipartite so $K_5$ is certainly not a subgraph. Or do you mean something different by "contain"? $\endgroup$
    – NovaDenizen
    Mar 2, 2014 at 15:18
  • 2
    $\begingroup$ @NovaDenizen There is a notion of containment for graphs which would identify $K_5$ as contained in your example - see en.wikipedia.org/wiki/Kuratowski's_theorem for the precise statement. I was taking the context of Kuratowski's Theorem as read, given it appears in the question. Really the definition reflects the intuition that modifications like the one you suggest don't change planarity - but the obvious things are the only ones you need to worry about. $\endgroup$
    – Mark Bennet
    Mar 2, 2014 at 15:35

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .