We are currently studying planar graphs and I have come across a review exercise that is proving to be more trouble than it's worth. The problem is as follows:
Let G = (V;E) be a planar graph with at most 12 vertices. Without using the 4-colour theorem or the 5 colour theorem (Theorems 13.4.1 or 13.4.2 in the Discrete Math book), prove that G has chromatic number at most 5.
I've got a few tools at my disposal, mostly that of Euler's equation of $|V|+|F|=|E|+2$, and it's later derivation of $|E| \leq 3|V|-6$. From these two, I can prove the six color theorem, as we can say by Handshake Lemma there must be at least one vertex of degree 5 or less in order to not break the $|E| \leq 3|V|-6$ inequality. As, with 12 vertices max, that would mean there is a max of 30 edges. However, I keep coming back to the fact that it seems I'm going to have to basically pseudo-prove the 5 color theorem again. Can I utilize the amount of vertices to my advantage, as it bounds vertices, edges, and faces?
Any help would be appreciated.
Hint: Show that has a vertex with degree at most 4 .
First try contradiction.
If all vertices of G are of at least 5 degree, by handshake lemma and ||≤3||−6, we know that it requires |V|=12, |E|=30, and G to be a 5-regular graph.
Except this case, it's not possible for all vertices of G to have at least 5 degree, so for other cases, G has at least a vertex v with deg(v) ≤ 4.
For the special case, use Brook's theorem.
For the more general case, prove by induction when n ≤ 12, remove v, which is similar to the proof of 5-colour theorem.