Brooks' theorem states that the chromatic number of a finite connected simple graph with at least one graph
vertex is at most the maximum vertex degree 
, unless the graph
is complete or an odd cycle, in which case 
colors are required (Brooks 1941).
Brooks' Theorem
See also
Chromatic Number, Vizing's TheoremExplore with Wolfram|Alpha
References
Brooks, R. L. "On Colouring the Nodes of a Network." Proc. Cambridge Philos. Soc. 37, 194-197, 1941. https://doi.org/10.1017/S030500410002168X.Lovász, L. "Three Short Proofs in Graph Theory." J. Combin. Th. Ser. B 19, 111-113, 1975.Skiena, S. Implementing Discrete Mathematics: Combinatorics and Graph Theory with Mathematica. Reading, MA: Addison-Wesley, p. 215, 1990.Referenced on Wolfram|Alpha
Brooks' TheoremCite this as:
Weisstein, Eric W. "Brooks' Theorem." From MathWorld--A Wolfram Resource. https://mathworld.wolfram.com/BrooksTheorem.html