# Doubt about chromatic number proof

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.

I've tried my own, and I've read the answers in here, here and this but I still have a big doubt using an induction proof as shown in 2.

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.

• Are you dead set on using induction? The easiest proof of this that I could think of would be to use the greedy coloring algorithm: en.wikipedia.org/wiki/Greedy_coloring May 30, 2020 at 22:05
• @Paralyzed_by_Time yes I though using it, but I'm requested on using induction. I've tought on using two scenarios: one in which the vertex I delete is not adjacent to the vertex with highest degree, and the other in which are two vertex of max degree adjacent and I delete one of them. Still, I'm wondering if there's a straight formulation, or why is the proposed in the previous questions valid and not dealing with this issue May 30, 2020 at 22:17

It’s entirely possible that after $$v$$ is removed, the maximum degree of the resulting graph $$H$$ is less than $$k$$. It doesn’t matter: the result being proved at that link is that if $$\Delta(G)\color{red}{\le}k$$, then $$G$$ is $$k$$-colorable. We assumed that $$\Delta(G)\le k$$, and removing a vertex cannot increase the maximum degree, so $$\Delta(H)\le k$$, and we can apply the induction hypothesis.
• Thank U for that!!! I was thinking that, $H$ should be $\Delta(H) \leq k$ instead $\Delta(H) = k$ and that would make more sense to me. I can see the demonstration sense, but the = was bothering me. May 30, 2020 at 22:20