You don't need to worry about odd cycles, because they can be colored with three colors and you are allowed four.
You need to justify three things:
- Show that the maximum possible degree is $4$ (not so bad, I think).
- Show that thine graph cannot be the complete graph on five vertices, i.e. that you will not get a clique (you can check by going backwards if you like).
- You don't care if you get an odd cycle.
The you can use Brook's theorem in all its glory.
For further information, this result is called Vizing's Theorem.
After some more thinking, I found a simple solution. We get it very quickly from two results which are well-known in graph theory, though for completeness I will include their proofs.
Lemma 1. A graph $G$ with minimum degree $k$ contains a cycle of length at least $k+1$.
Proof. Take the longest path $v_0, v_1, v_2, \dots, v_\ell$ in $G$. The vertex $v_0$ has at least $k$ neighbors, and all of them must be other vertices on the path, because otherwise we could extend the path and make it even longer. The last of $v_0$'s neighbors on the path must be at least as far as $v_k$ (since there's $k$ of them), so we get a cycle of length at least $k+1$ by following the path from $v_0$ to $v_0$'s last neighbor, then taking the edge back to $v_0$.
Conversely, if the longest cycle in a graph $G$ has length $k$, then it has a vertex of degree $k-1$ or less. What's more, in every subgraph $H$ of $G$, the longest cycle has length $k$ or less (if it's a cycle in $H$, it's a cycle in $G$, too). So $H$ must have a vertex of degree $k-1$ or less.
A graph with this property - every subgraph has a vertex of degree $k-1$ or less - is called $(k-1)$-degenerate.
Lemma 2. A $(k-1)$-degenerate graph $G$ has chromatic number at most $k$.
Proof. We induct on the number of vertices in $G$. When $G$ has $k$ vertices or fewer, we can $k$-color $G$ by giving all the vertices different colors.
Otherwise, let $v$ be a vertex of degree $k-1$ or less. $G-v$ is also $(k-1)$-degenerate (every subgraph of $G-v$ is a subgraph of $G$) and has one fewer vertex, so by induction $G-v$ is $k$-colorable. We can $k$-color $G$ by starting with the $k$-coloring of $G-v$, then giving $v$ a color distinct from the colors on its neighbors (which eliminates at most $k-1$ options).
Putting together the two lemmas: a graph with circumference $k$ is $(k-1)$-degenerate, so it has chromatic number at most $k$. The chromatic number is at most the circumference.
Best Answer
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:
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.