All vertices except $d+1$ have degree at most $d$, then it is ($d+1$)-colorable.

Question

Let $G$ be a connected graph such that all vertices but $d+1$ have degree at most $d$. Prove that $G$ is ($d+1$)-colorable.

I am trying to prove this generalization of ''if the maximum degree is $d$, then $G$ is $(d+1)$-colorable.''

I tried induction on $n$ but could not decide the range of $d$. Also, I tried several other things using the above fact about graphs with a maximum degree $d$ such as coloring the whole graph part by part and then changing colors when new edges between any two parts are added.

Answer 1

First color the first $d+1$ vertices with different colors.

After this paint the other vertices one by one, since each of these have at most degree $d$ there is always going to be a color that is not present among its neighbours that have already been colored.