Why should I care about Brooks' Theorem? Brooks' Theorem says that 

If $G$ is any connected graph that's neither complete nor an odd cycle, then $\chi(G) \leq \Delta(G)$

(Where $\chi$ is the colouring number and $\Delta(G)$ is the maximum degree of $G$.)
Why is this an important result? If you just colour $G$ using the greedy algorithm (colour each vertex with the first available colour), you get a colouring using at most $\Delta(G) + 1$ colours. Brooks' Theorem only improves on this by one, so what's the big deal?

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.
