Proving Brooks' Theorem in Graph Theory Okay, so I'm mainly concerned with this lemma we do beforehand (although a similar, albeit less severe, issue comes up in the actual proof of Brooks' Theorem). 
"Let $ G $ be a connected graph with maximum degree $ \Delta $ which has a vertex of degree less than $ \Delta $. Then the chromatic number of $ G $ is at most $ \Delta $."
So the proof goes like this: we pick a vertex $ x $ of degree less than $ \Delta $ and for each vertex we determine its distance to $ x $. Then we look at the subgraph induced by the furthest vertices. This has max degree at most  $\Delta - 1 $ since all of its vertices are adjacent to a vertex closer to $ x $. Therefore we can colour it with $ \Delta $ colours (since we can colour a graph of max degree $ \delta $ with $ \delta + 1 $ colours). 
Now consider the vertices one step closer to $ x $. Each is adjacent to a vertex closer to $ x $ so we need only $ \Delta $ colours to colour these. 
Continue until we get to $ x $, then since $ x $ has degree $ \Delta - 1 $ we have a spare colour. QED, supposedly. 
But how do we know that the colourings agree? For instance, how do we know that when we colour in this way, a vertex of distance $ n - 1 $, where $ n $ is the max distance from $ x $, is not coloured the same way as a vertex of distance $ n $? I'm having trouble even trying to prove that this holds if the max distance is 2, let alone prove it in general. 

When you color a vertex $v$ in layer $k$ then it is adjacent to at most $\Delta-1$ vertices in total in layers $k,k+1$ (and some yet uncolored vertices in layer $k-1$). Therefore $v$ is adjacent to at most $\Delta-1$  vertices already colored and you have one color available to color $v$ greedily.
