The problem is:

Let $G$ be a connected planar graph with less than 12 vertices. a) Prove that G has a vertex with degree $\leq 4$. b) Prove that $\chi (G) \leq 4$. (Do not use the Four Color Theorem)

I did prove part a) satisfactorily I think at least =/

My question is about part b).

I am thinking showing part b) by contradiction may work. I am thinking perhaps something concerning a particular vertex with degree at most $4$, deleting this vertex, showing a $4$ coloring is still possibly, any hints? =/

I am also thinking I could use Euler's Formula but I am not sure of how I would relate $n+r-e=2$ back to the chromatic number.

(I should have stated it said to do the problem without the four color theorem)


1 Answer 1


I think you can change the standard proof of "any planar graph is 5 colorable" to this case.

Assume by contradiction that this is not true. Pick a planar graph which is not $4$ colorable, and has at most 11 vetices, with the smallest number of vertices

Now, by the previous part, this graph has a vertex of degree at most $4$. Remove that vertex. The smaller graph is 4 colorable.

Add the vertex back in. It is connected to 4 vertices. If two have the same color, you are done. If all four vertices have different colors, repeat the argument from the 5 color theorem to recolor the four neighbours..

  • $\begingroup$ Ok thank you very much. I have been behind in this class and I am trying to get caught up to save my grade, if the gods shall be it so lol $\endgroup$
    – user43138
    Dec 7, 2012 at 3:15
  • 1
    $\begingroup$ Two bugs: (a) "at most 12 vetices" -> "at most 11 vertices". (E.g. the icosahedron is an example of a 5-regular 12-vertex planar graph.) (b) "has a vertex of degree $4$" -> "has a vertex of degree at most $4$". $\endgroup$ Aug 18, 2013 at 7:08

Your Answer

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