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:
|
--C--
| | |
--B-----A-----D--
| | |
--E--
|
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.
For small $\Delta$, Brooks's theorem is very strong. For example, it means that almost all $3$-regular graphs have chromatic number $3$: only those with a $K_4$ component can have chromatic number $4$, only the bipartite ones can have chromatic number $2$, and both of these are rare.
For large $\Delta$, Brooks's theorem is primarily interesting not because it's a particularly useful thing to say, but because it is often the best thing we can say. (The big deal is that we can't do better.) There are some results, and more conjectures, about strengthenings of Brooks's theorem:
When can we guarantee that $\Delta-1$ colors are enough? Clearly we need to assume the graph is $K_\Delta$-free. For large $\Delta$, this is enough; it's conjectured that this is enough for $\Delta \ge 9$.
When is it easy to test if a graph is $(\Delta+1-k)$-colorable? There is a polynomial-time algorithm if $k^2 + k \le \Delta$ (so for about $\Delta - \sqrt{\Delta}$ colors) and the problem is NP-complete if $k^2 + k > \Delta$.
For more details of these, the paper Brooks' theorem and beyond by Cranston and Rabern is a good source.
Best Answer
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:
The you can use Brook's theorem in all its glory.
For further information, this result is called Vizing's Theorem.