# A problem in graph theory related to the chromatic number

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)$.

-

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)$.