# Yet Another Proof of Brooke's Theorem

A classical result from Graph theory is that given $$G$$ an undirected graph:

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. It is reasonably straightforward to prove the result with this idea: every node has at most $$\Delta(G)$$ neighbors, hence the highest color you could possibly pick is $$\Delta(G) + 1$$. This is the result you will probably find in most books and courses in graph theory. I was talking with some friends the other day, when this topic came up and we thought of this proof.

For completeness, I will include a few definitions here:

Definition: The neighborhood of a node $$v \in V(G)$$ is

Definition: the closed neighborhood of a node $$v \in V(G)$$ is

Concretely, the idea lies in the following realization: given a minimal coloring $$f : V(G) \to [\chi(G)]$$, $$\exists v \in V(G) : \#f(N[v]) = \chi(G)$$. What does this mean? This means that there exists a vertex such that the number of colors in the closed neighborhood of $$v$$ is exactly $$\chi(G)$$. Assuming that the above statement is true, notice that $$\#N[v] = dg(v) + 1$$, hence:

Which is precisely Brooke's theorem. So, if we can find a way to prove that $$\exists v \in V(G) : \#f(N[v]) = \chi(G)$$, we're done. Let's put up the formal statement:

Lemma: Given $$G$$ an undirected graph, $$f$$ a minimal coloring for $$G$$, $$\exists v \in V(G) : \#f(N[v]) = \chi(G)$$.

Proof: Suppose that $$\forall v \in V(G) : \#f(N[v]) \neq \chi(G)$$. Clearly, $$\#f(N[v])$$ can not be greater than $$\chi(G)$$, for such an event would contradict $$f$$ being a minimal coloring for $$G$$. Hence, we have that every closed neighborhood of $$G$$ has $$\#f(N[V]) \lt \chi(G)$$. Let $$C_k = \{v \in V(G) : f(v) = k\}$$, where $$k \in [\chi(G)]$$; these $$C_k$$ are the nodes colored with color $$k$$. Just for succinctness, let's call $$C = C_{\chi(G)}$$ (the nodes colored with the last color).

Given any node $$w \in C$$, we can change its color to a different, lower color not used in its neighborhood, because $$\#f(N[w]) \lt \chi(G)$$ (this means that not every color is used in the neighborhood, hence we can at least take $$\chi(G) - 1$$). Call $$c_w$$ this lower color we chose. Notice that there are no conflicts with any neighbors by construction.

Let's define $$g : V \to [\chi(G) - 1]$$ as

Let's see that this is a coloring: given any $$e = (v, w) \in E(G)$$, we want to check that $$g(v) \neq g(w)$$. Suppose that $$g(v) = g(w)$$, then there's three possible cases:

1. $$v \in C \wedge w \in C$$: $$C$$ was the set of nodes colored with $$\chi(G)$$ according to $$f$$, which was actually a coloring by hypothesis. Hence, this can not happen, as it would contradict $$f$$ being a proper coloring.
2. $$v \not \in C \wedge w \not \in C$$: we have that $$g(v) = f(v) \wedge g(w) = f(w)$$, thus $$f(v) = f(w)$$, this would contradict the hypothesis that $$f$$ is a proper coloring.
3. $$v \in C \wedge w \not \in C$$: by definition, we have that $$w \in N[v]$$, and we picked $$g(v)$$ such that it wouldn't conflict with any of its neighbors. Thus, this can't happen either.

Finally, we have proven that $$g$$ is a coloring!. However, this means we have built a coloring of $$G$$ such that it uses less colors than $$\chi(G)$$. This is absurd, and thus $$f$$ must not have been a minimal coloring.