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)$.
A problem in graph theory related to the chromatic number
-2
$\begingroup$
graph-theory
1 Answers
2
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)$.