Prove that if $G$ is connected, not the complete graph and $\Delta(G) > 2$ then the chromatic number of G is at most $\Delta(G)$.
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.
Here's how it works:
- Anybody can ask a question
- Anybody can answer
- The best answers are voted up and rise to the top
Using Brook's theorem, if a graph is not complete or cyclic then $\chi(G)\leq\triangle(G)$. Since $\triangle(G)>2$, therefore $G$ is not cyclic. Hence $G$ is not complete or cyclic. Thus, $\chi(G)\leq\triangle(G)$.