Chromatic number of Simple Connected Planar Graph

Question

The chromatic number of a Simple Connected Planar Graph is $\le 6$.

How do I proceed to prove this?

Answer 1

I'm giving you some hints.

Theorem: For a connected, simple planar graph $G=(V,E)$, $ \chi(G) \leq 6$.

Proof Sketch: We prove via induction on $|V(G)|=n$. The base case $1 \leq n \leq 6$ is trivial, since a graph on $6$ or less vertices can always be coloured with $6$ colours. Suppose that $G$ has $k \geq 6$ vertices and $G$ is $6$-colourable. Consider any simple, connected planar graph $G'$ on $k+1$ vertices. $G'$ contains a $v' \in V(G')$ with $deg(v') \leq 5$ (This is the "tricky" part. Why is this true? Hint: Consider the average degree and use Eulers Formula). What happens if we remove $v'$ from $G'$?