# Yet Another Proof of Brooke's Theorem

A classical result from Graph theory is that given $$G$$ an undirected graph: \chi(G) \leq \Delta(G) + 1 Where $$\chi(G)$$ is the minimum number of colors required to paint the nodes of $$G$$ with the usual restriction that no node has the same color as any of its neighbors, and $$\Delta(G) = max_{v \in V(G)}(dg(v))$$, that is, the maximum degree. This result is known as Brooke’s Theorem. The usual way to prove this result is to use the Greedy coloring algorithm: go through every node, and pick the lowest color not yet used by any of its neighbors.

© Julian Bayardo Spadafora 2015-2020