# Vertex coloring a graph with a unique vertex of maximum degree

by Aidan   Last Updated September 11, 2019 18:20 PM - source

Suppose a graph $$G$$ has a unique vertex of maximum degree, and let $$d_2$$ be the second-highest degree in $$G$$. Show that $$\chi(G)\leq d_2+1$$.

I'm trying contrapositive and making some argument about partitioning into strictly more than $$d_2+1$$ independent sets, but I do not see how that points me toward a non-unique $$\Delta$$. Also since the problem does not specify connected I can't (and don't see how it relates anyway) use Brooks' theorem to obtain $$\Delta$$ as opposed to $$\Delta+1$$ for an upper bound.

Tags :