By (long) induction on the number of vertices:
If there is a vertex of degree less than $4$, then remove it, color the rest of the graph (by the induction hypothesis) and pick a color for the remaining vertex.
Otherwise the graph is 4-regular. Select a vertex $A$ and its neighbors $B,C,D,E$ (in order) according to your favorite plane drawing of the graph:
| | |
| | |
Now suppose there is a simple cycle in the graph that contains the edges BA and AD and does not contain C or E. Choose such a cycle of minimal length. Because of this minimality, there are no edges between vertices in the cycle other than those that make up the cycle.
The chosen cycle divides the graph into a region inside the cycle and a region outside the cycle. (This is where planarity is used). Color the inside region and the outside region separately, and then permute the "inside" colors such that C and E have the same color.
It remains to color the vertices in the cycle, but that can be done by the following easy lemma:
Suppose we have a cyclic graph and for each vertex we have a choice of two colors for it (not necessarily the same two colors at each vertex), except that there is one vertex where three colors are allowed. Then a valid coloring for the cycle can be selected.
If a cycle as described above does not exist, then removing the vertices C, A, and E must cause the graph to fall apart into a left and a right part (containing B and D, respectively). Recursively first color the left part together with CAE, and then the right part together with CAE, and then if necessary permute the colors in one of the parts such that they match at C, A, and E.
The once case where this might not work is if one of the part colorings (say, the left one) assigns the same color to C and E, and the other one doesn't. But that's easily repaired: If C and E are both connected to the right part, then we can add an edge between them while we re-color the left part without exceeding the degree maximum. And if one of them is not connected to anything on the right, then we can simply change its color in the right-side coloring to match that of the other.