Prove that any planar graph of maximum degree $4$ has chromatic number at most $4$. (The $4$-color theorem cannot be used here)

So first I use;

$\text{$K_5$ is not planar.}\tag2$

and finally

$\text{(Brooks 1941). If $G$ is a connected graph other than a clique or an odd cycle then,}$ $\chi(G)\le\Delta(G).\tag3$

and the question is answered, do you agree ?

  • 3
    $\begingroup$ You have as a hypothesis that the maximum degree is four, so the theorem about containing a vertex of degree at most five adds nothing. If this is homework, the use of Brooks Theorem is probably not the intended route to the proof. $\endgroup$ – Austin Mohr Jun 27 '17 at 17:32
  • $\begingroup$ @AustinMohr Of course, superfluous. I tried first for the general case, but are the other $2$ enough for the claim ? $\endgroup$ – pigeon whole Jun 27 '17 at 17:35
  • 1
    $\begingroup$ Brooks' Theorem will certainly do it, but as I said, I don't think that was the intent of the question. If you're going to use a big powerful theorem, why not just cite the Four Color Theorem? $\endgroup$ – Austin Mohr Jun 27 '17 at 19:05
  • $\begingroup$ @AustinMohr That one is not allowed. $\endgroup$ – pigeon whole Jun 27 '17 at 20:42
  • 1
    $\begingroup$ consider a graph on n vertices as 4 colorable, now add a vertex and prove it remains 4 colorable $\endgroup$ – shai horowitz Jun 27 '17 at 21:01

By (long) induction on the number of vertices:

If there is a vertex of degree less than $4$, then remove it, color the rest of the graph (by the induction hypothesis) and pick a color for the remaining vertex.

Otherwise the graph is 4-regular. Select a vertex $A$ and its neighbors $B,C,D,E$ (in order) according to your favorite plane drawing of the graph:

  |     |     |
  |     |     |

Now suppose there is a simple cycle in the graph that contains the edges BA and AD and does not contain C or E. Choose such a cycle of minimal length. Because of this minimality, there are no edges between vertices in the cycle other than those that make up the cycle.

The chosen cycle divides the graph into a region inside the cycle and a region outside the cycle. (This is where planarity is used). Color the inside region and the outside region separately, and then permute the "inside" colors such that C and E have the same color.

It remains to color the vertices in the cycle, but that can be done by the following easy lemma:

Suppose we have a cyclic graph and for each vertex we have a choice of two colors for it (not necessarily the same two colors at each vertex), except that there is one vertex where three colors are allowed. Then a valid coloring for the cycle can be selected.

If a cycle as described above does not exist, then removing the vertices C, A, and E must cause the graph to fall apart into a left and a right part (containing B and D, respectively). Recursively first color the left part together with CAE, and then the right part together with CAE, and then if necessary permute the colors in one of the parts such that they match at C, A, and E.

The once case where this might not work is if one of the part colorings (say, the left one) assigns the same color to C and E, and the other one doesn't. But that's easily repaired: If C and E are both connected to the right part, then we can add an edge between them while we re-color the left part without exceeding the degree maximum. And if one of them is not connected to anything on the right, then we can simply change its color in the right-side coloring to match that of the other.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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