Theorem 4.4.5. Brooks' Theorem.
Any graph \(G\) satisfies \(\chi(G) \le \Delta(G)\text{,}\) unless \(G\) is a complete graph or an odd cycle, in which case \(\chi(G) = \Delta(G) + 1\text{.}\)
Any graph \(G\) satisfies \(\chi(G) \le \Delta(G)\text{,}\) unless \(G\) is a complete graph or an odd cycle, in which case \(\chi(G) = \Delta(G) + 1\text{.}\)