Prove that a planar graph has four coloring There is a theorem which says that every planar graph can be colored with five colors. It can also be colored with four colors. How can I prove that any planar graph with max degree of $4$, has a four coloring?
Can someone help me prove this?
 A: [Extended hint, posted as answer because unwieldy as a comment]
Consider a vertex $v$ in your planar graph, so $\deg(v)\le4$. 
If $v$ has $3$ or few neighbours, there are at most $3$ colours adjacent to $v$, so we can pick the fourth colour for $v$.
Suppose $v$ has $4$ neighbours. We're only in trouble if all $4$ neighbours have different colours. But that's only a possible problem if all $4$ neighbours have degree $4$ (otherwise, if one of the neighbours had degree $\le 3$, we could ignore it, colour $v$, then recolour the neighbour as above).
So any potential problem reduces to having $\deg(v)=4$, with all $4$ neighbours having degree $4$, and not being able to recolour.  Can you think of a way of bringing $K_5$ into the argument? What do you know about $K_5$ and planar graphs?
Edit: While the statements above are true, the proof I'd sketched out in my head didn't work.
A: Choose a vertex $v$ in $G$ and inductively $4$-color $G - v$. If the neighbors of $v$ do not represent all $4$ color classes, choose $v$'s color to create a legal $4$-coloring of $G$.
Otherwise, each of $v$'s neighbors is colored a different color, and suppose they are labeled $v_1,v_2,v_3,v_4$ clockwise in a planar drawing of $G$.
Now, we try to change $v_1$'s color to match $v_3$'s, propagating any forced color changes through the graph. If this is possible, then we can color $v$ with $v_1$'s original color. If it is not possible, then there is an alternating path of the colors of $v_1$ and $v_3$ connecting $v_1$ to $v_3$. Since that path closes a simple curve separating $v_2$ from $v_4$, we can swap $v_2$'s color to $v_4$'s without issue, creating a legal $4$-coloring of $G$.
