Show that Brooks' theorem is equivalent to the following: If G is k-critical graph (k ≥ 4) which is not complete, then 
$\space\space 2\varepsilon ≥ \nu(k-1) + 1$
, where $\nu = |V(G)|, \varepsilon = |E(G)|$
*Brooks' theorem: For any connected undirected graph G with maximum degree Δ, the chromatic number of G is at most Δ unless G is a complete graph or an odd cycle, in which case the chromatic number is Δ + 1.
 A: 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.
