# Brooks' theorem

## From Wikipedia, the free encyclopedia

In graph theory, **Brooks' theorem** states a relationship between the maximum degree of a graph and its chromatic number. According to the theorem, in a connected graph in which every vertex has at most Δ neighbors, the vertices can be colored with only Δ colors, except for two cases, complete graphs and cycle graphs of odd length, which require Δ + 1 colors.

The theorem is named after R. Leonard Brooks, who published a proof of it in 1941.^{[1]} A coloring with the number of colors described by Brooks' theorem is sometimes called a *Brooks coloring*^{[2]} or a Δ-*coloring*.^{[3]}