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. 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
$$
N(v) = \{w \in V(G) : (v, w) \in E(G)\}
$$
**Definition:** the closed neighborhood of a node $v \in V(G)$ is
$$
N[v] = N(v) \cup \{v\}
$$
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:
$$
\chi(G) = \#f(N[v]) \leq dg(v) + 1 \leq \Delta(G) + 1
$$
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
$$
g(v) =
	\begin{cases}
		c_v & v \in C \\
		f(v) & \text{otherwise}
	\end{cases}
$$
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.