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.

- Serverfault Help
- Superuser Help
- Ubuntu Help
- Webapps Help
- Webmasters Help
- Programmers Help
- Dba Help
- Drupal Help
- Wordpress Help
- Magento Help
- Joomla Help
- Android Help
- Apple Help
- Game Help
- Gaming Help
- Blender Help
- Ux Help
- Cooking Help
- Photo Help
- Stats Help
- Math Help
- Diy Help
- Gis Help
- Tex Help
- Meta Help
- Electronics Help
- Stackoverflow Help
- Bitcoin Help
- Ethereum Help