Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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 ?

share|improve this question
7  
Why would a graph be $4$-colorable if it doesn't contain $K_5$ or $K_{3,3}$? –  TMM Mar 2 at 13:15
1  
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? –  TMM Mar 2 at 13:22
    
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. –  Archimedix Mar 2 at 13:44
    
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. –  TMM Mar 2 at 14:19
    
Good point. I can see that I'd likely run into a dead end if I extend the subgraph by two vertices at once. However, if I just take all but one vertex of my current subgraph plus a yet unconsidered vertex such that I get a $K_5$ or $K_{3,3}$ minus one vertex and color the new one with the excluded vertex's color, I imagine I could sort of flood-fill the entire graph without running into a dead end. –  Archimedix Mar 2 at 15:01

1 Answer 1

up vote 3 down vote accepted

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

share|improve this answer
    
Do you have a visualization of a simple example for such a graph ? –  Archimedix Mar 2 at 13:41
    
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"? –  NovaDenizen Mar 2 at 15:18
    
@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. –  Mark Bennet Mar 2 at 15:35

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.