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.


1 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.


You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .