Vertex coloring a graph with a unique vertex of maximum degree

Question

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.

Answer 1

Without loss of generality, $G$ is connected. Let $v$ be the unique vertex of maximum degree, and color $G-v$ with as few colors as possible. By Brooks's theorem, this will require either $d_2$ or $d_2+1$ colors. If it is $d_2$, we have only to color $v$ with some color not already in the set. If it takes $d_2+1$ colors, then $G-v$ is either a complete graph or an odd cycle.

Take it from here.

Answer 2

Assume you have $d_2+1$ colours available. Colour the vertex of maximum degree arbitrarily. Pick further points one by one and colour each one with a colour not already used on one of its adjacent points. Since each point after the first has degree at most $d_2$, there's always an available colour.