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
Proving Brook's theorem with the given result is easy.
All we have to do is show every non-complete connected graph $G$ which cannot be colored with $k+1$ colors must contain a vertex of degree at least $k+1$.
So let $G=G_1,\dots, G_m=H$ be a sequence of graphs obtained from the previous by removing non-cut vertices. It is easy to show that we eventually reach a $k$-critical graph, we stop at this point. So $H$ is a $k$-critical graph. If $H$ is complete then we are done, since at least one vertex must have been connected to one of the previously deleted vertices. So $G$ contains a vertex of at least $k+1$, if $H$ is not complete then notice that by the theorem $\frac{2\epsilon}{\nu}\geq k + \frac{1}{\nu}$ and so $\frac{2\epsilon}{\nu}>k$, since the average degree of $H$ is greater than $k$ it must contain a vertex of degree at least $k+1$.
We now prove the given result using Brooke's theorem.
We take a connected $k$-critical non-complete graph and prove that the sum of its degrees is at least $(k-1)\nu+1$.
It suffices to prove a vertex of degree at least $k$ exists and that every vertex has degree at least $k-1$.
The first part is clearly corollary of Brook's theorem. ( if every vertex had degree at most $k-1$ then the graph would be $k-1$-colorable by brook's theorem).
The second part is a consequence of the criticallity.
Take a vertex $v\in G$. Notice that $G\setminus v$ can be colored using $k-1$ colors, take one such coloring. If $v$ had degree less than $k-1$ then there would exist a color such that $v$ is not connected to any vertex of that color. And therefore $G$ would be $k-1$ colorable too.
We conclude every vertex has degree at least $k-1$ and at least one vertex had degree at least $k$. It follows $2\epsilon\geq \nu(k-1)+1$ as desired.