I'm in a discrete math course and was trying to prove the following theorem:
A graph G with $\Delta(G) = k$ ($\Delta(G)$ is the max vertex degree) is $(k+1)-$coloreable.
In the induction step, when we delete a vertex v of the graph $G$ with $\Delta(G) = k$: What garantees me that once the vertex is deleted, $\Delta(G)$ is stil k? As they show that $\Delta(G') = k$, what garantees that?
PD: pardon my english, I'm not native speaker.