Special Case of Brooks' Theorem on an Incomplete Regular Graph? I'm trying to come up with a proof of Brooks' Theorem (an incomplete connected graph which is not an odd cycle can be vertex-coloured with a set of colours the size of the maximum degree of the graph) which is more intuitive than the one I currently have.
I have managed (by inducting on the number of vertices, and treating 1- and 2-connected cases separately, to reduce to the case where $G$ is regular. Is there a good way to treat this case? 
 A: When I was teaching Brooks's theorem, I ultimately went with a proof based on the one found on this page, modifying some of the cases slightly.

You have already dealt with the case where $G$ is not regular. But I'm worried that your proof of this case is not very clean if it requires considering $2$-connectivity. 
It's enough to say that if $G$ is connected and has a vertex $v$ with $\deg(v) < \Delta(G)$, then we can order the vertices carefully and greedily color with respect to that ordering. The page I link to suggests finding a spanning tree $T$ of $G$, and ordering vertices in decreasing order of distance from $v$ in $T$, putting $v$ last.
Now if we greedily color with respect to this order, every vertex has at most $\Delta(G)-1$ colored neighbors: either it is not $v$, and has a neighbor which is closer to $v$ in $T$ and therefore not colored, or else it is $v$, and has degree at most $\Delta(G)-1$. So we use at most $\Delta(G)$ colors.
(By the time you prove Brooks's theorem, you should have already proven that all graphs with maximum degree $\Delta(G)$ can be colored with $\Delta(G)+1$ colors. This is done in the same way, except without carefully putting the vertex $v$ last.)

The cases where $\kappa(G)=1$ and $\kappa(G) = 2$ are very similar. We find a vertex cut and combine two partial colorings of the graph.
When $\kappa(G)=1$, let $\{v\}$ be a vertex cut and suppose that $G-v$ splits into two parts $G_1$ and $G_2$ with no edges between $G_1$ and $G_2$. Color $G_1+v$, color $G_2+v$, and permute the colors on $G_2+v$ (if necessary) so that the two colorings agree on $v$.

The $\kappa(G)=2$ case is harder. My approach is different from any proofs that I've found, because it uses randomness; but this is a useful technique to mention at some point, and I think this approach is cleaner.
When $\kappa(G)=2$, let $\{v,w\}$ be a vertex cut and suppose that $G-\{v,w\}$ splits into two parts $G_1$ and $G_2$ with no edges between $G_1$ and $G_2$. If there is an edge $vw$, then as before we can color $G_1 + \{v,w\}$, $G_2 + \{v,w\}$, and then permute one of the colorings so that they agree on $\{v,w\}$. This generalizes to coloring a clique-sum of two graphs.
If $v$ and $w$ are not adjacent, then color $G_1$ and $G_2$ and randomly permute the colors on $G_2$. Now try to complete the coloring to a coloring of $G$ by picking colors for $v$ and $w$.
This fails for $v$ if its $k$ neighbors in $G_1$ and $\Delta(G)-k$ neighbors in $G_2$ together include all $\Delta(G)$ colors. This happens with probability $\binom{\Delta(G)}{k}^{-1}$ which is at most $\frac1{\Delta(G)}$. The same is true for $w$. Altogether, the probability of failure is at most $\frac1{\Delta(G)} + \frac1{\Delta(G)} = \frac{2}{\Delta(G)}$ by the union bound. 
If $\Delta(G)=2$, then $G$ is a cycle and we can take care of that separately. If $\Delta(G)>2$, then the probability of failure is less than $1$, so a way to succeed and color all of $G$ exists.

Finally, if $\kappa(G) \ge 3$, then we mirror the proof of the first case by choosing an ordering and coloring greedily. 
Let $v$ be any vertex. If all $\Delta(G)$ of its neighbors are adjacent, they form a clique on $\Delta(G)+1$ vertices and we're in one of the exceptional cases.
So $v$ has neighbors $w_1, w_2$ that are not adjacent. Because $\kappa(G)\ge 3$, $G - \{w_1,w_2\}$ is still connected. Find a spanning tree $T$ of $G - \{w_1,w_2\}$, and order the vertices as follows: $w_1,w_2$ go first, all other vertices are sorted in order of decreasing distance from $v$ in $T$, putting $v$ last.
We color greedily. Since we begin with $w_1$ and $w_2$, which are not adjacent, they get the same color. From then on, each non-$v$ vertex has a neighbor closer to $v$ in $T$ which is still uncolored, so it has at most $\Delta(G)-1$ colored neighbors and we can give it a color. When we get to $v$, two of its neighbors ($w_1$ and $w_2$) have been given the same color, so there is a color free to use on $v$.
