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.

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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)

share|cite|improve this question
up vote 2 down vote accepted

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 12 vetices, with the smallest number of vertices

Now, by the previous part, this graph has a vertex of degree $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..

share|cite|improve this answer
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 – Frudrururu Dec 7 '12 at 3:15
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$". – Douglas S. Stones Aug 18 '13 at 7:08

Your Answer


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.