April 30, 2016

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. Read more