Teorema (Brooks)

Seja $G = (V,E)$ um grafo conexo que não é nem um ciclo ímpar, nem completo. Então,

$$\chi (G) \leq \Delta (G).$$

Demonstração:

Faremos essa prova por indução sobre o número de vértices de $G$, $|G|$. Observando que essa desigualdade trivialmente se verifica se $G$ tem $0$, $1$ ou $2$ vértices. Além disso, se $\Delta(G) \leq 2$, é facilmente verificado que $G$ é um caminho ou um ciclo. Nesse último caso, esse ciclo deve ser par por hipótese. Em qualquer situação, $G$ pode ser colorido com duas cores.

Portanto, podemos nos restringir ao caso em que $\Delta(G) \geq 3$ e supor que o resultado se verifica para grafos com menos que $|G|$ vértices. Por absurdo, porém, iremos supor que $\Delta(G)$ cores não são suficientes para colorir $G$.

Nesse sentido, fixe $v\in V$ qualquer e considere o subgrafo $H = G\setminus v$. Por hipótese indutiva, então, toda componente conexa $H'$ de $H$ pode ser colorida com $\Delta(H') \leq \Delta (G)$ cores se não for um ciclo e nem um grafo completo. Nesse últimos dois casos, $H'$ pode ser colorido com $\Delta(H') + 1$ cores, conforme discutido acima. Ainda assim, se $H'$ é um ciclo ímpar, $\Delta(H') + 1 = 2+1 = 3 \leq \Delta(G)$. Se $H'$ for um grafo completo, também vale que $\Delta(H') + 1 \leq \Delta(G)$, pois $v$ tem algum vizinho em $H'$ - vizinho esse que deve ter (em $G$) grau maior ou igual a $(|H'| - 1)+1 = |H'| > \Delta(H')$. Em suma, o grafo $H$ pode ser colorido com $\Delta(G)$ cores, ao escolhermos colorações para suas componentes conexas como nos casos descritos. Como $G$ não pode ser colorido com essa quantidade de cores, entretanto, verifica-se a seguinte observação:

$(*)$ Toda coloração de $H$ com $\Delta(G)$ cores deixa todos os vizinhos de $v$ com cores diferentes, e há um vizinho de cada cor. Em particular, o grau de $v$ em $G$ é máximo.

A respeito das possíveis formas de colorir o subgrafo $H$ com $\Delta(G)$, descreveremos mais três observações. Vejamos

• Observação 1: Fixada uma coloração de $H$ com cores em $\{1,2,\dots,\Delta(G)\}$, denotaremos por $H_{i,j}$ o subgrafo de $H$ induzido pelos vértices que receberam cores $i$ e $j$. Vamos mostrar que, se $i \neq j$, os vizinhos $v_i$ e $v_j$ de $v$ em $H$ que receberam essas cores pertencem a uma mesma componente conexa de $H_{i,j}$. Mas isso é imediato: se $v_i$ pertencesse a uma componente e $v_j$ em outra, definimos outra coloração em $H$ trocando as cores $i$ e $j$ na componente de, digamos, $v_j$. Nessa nova coloração, porém, $v$ tem dois vizinhos de cor $i$ e não tem vizinhos de cor $j$, contradizendo o que estabelecemos com a afirmação $(*)$.
• Observação 2: Fixada uma coloração de $H$ com cores em $\{1,2,\dots,\Delta(G)\}$, utilizando a notação da observação anterior, seja $C_{i,j}$ a componente de $H_{i,j}$ que contém os vizinhos $v_i$ e $v_j$ de $v$. Afirmamos que essa componente é, na verdade, um caminho. Para mostrarmos isso, observamos primeiro que ela contém um caminho $P$ entre $v_i$ e $v_j$. Inclusive, considere $P$ com o menor número de vértices possível com essa propriedade. Visando concluir que $V(C_{i,j}) = V(P)$, basta mostrarmos que nenhum vértice de $P$ tem um vizinho em $H\setminus V(P)$ com cor $i$ ou $j$. Isso é facilmente verificado nas extremidades de $P$. Por exemplo, o vértice $v_i$ tem no máximo $\Delta(G)-1$ vizinhos em $H$, pois seu grau em $G$ é no máximo $\Delta(G)$ e um de seus vizinhos é $v$. O vizinho de $v_i$ em $P$ tem cor $j $ por definição. Se ele possui outro vizinho de cor $j$, então ele não possui vizinho de alguma cor $k \neq i,j$. É possível, então, trocar sua cor por $k$, mas geraria uma coloração em que $v$ não tem vizinhos de cor $i$, contradizendo o que estabelecemos com a afirmação $(*)$. Da mesma forma, $v_j$ tem um único vizinho de cor $i$, que é seu vizinho em $P$. Suponha finalmente que algum vértice $u\in V(P)$, que não $v_i$ ou $v_j$, tem um vizinho $w$ de cor $i$ ou $j$ que não pertence a $P$. A figura abaixo ilustra esse cenário. Ora, o próprio $u$ tem cor, digamos, $i$. Assim, três de seus vizinhos têm cor $j$: seus dois vizinhos em $P$ (pela escolha desse caminho) e $w$. O grau de $u$, entretanto, é no máximo $\Delta(G)$. Novamente, então, existe $k\neq i,j$ uma cor que não é atribuída a nenhum vizinho de $u$. Colorindo $u$ com essa cor, a minimalidade de $P$ nos garante que, mediante essa nova coloração, os vértices $v_i$ e $v_j$ se encontram em componentes conexas distintas de $H_{i,j}$, contradizendo a observação acima.

• Observação 3: Fixe uma coloração com cores em $\{1,2,\dots,\Delta(G)\}$ e, para cada par $1 \leq i,j \leq \Delta(G)$, sejam $v_i$, $v_j$, $H_{i,j}$ e $C_{i,j}$ como nas observações acima. Argumentamos que, se $k$ é uma terceira cor, então $C_{i,j}$ e $C_{i,k}$ possuem apenas o vértice $v_i$ em comum. De fato, uma eventual intersecção entre os caminhos $C_{i,j}$ e $C_{i,k}$, a menos do vértice $v_i$, não pode ocorre nem no vértice $v_j$ e nem no vértice $v_k$, pois as cores desses vértices são diferentes. Logo, um eventual vértice $u\in V(C_{i,k})\cap V(C_{i,j})\setminus \{v_i\}$ possui cor $i$, dois vizinhos de cor $j$ e dois vizinhos de cor $k$. Novamente, como o grau de $u$ é no máximo $\Delta(G)$, existe $l \neq i,j,k$ uma cor que não é recebida por nenhum vizinho de $u$. Colorindo $u$ com tal cor, obtemos uma coloração dos vértices de $H$ em que $v_i$ e $v_j$ pertencem a componentes conexas diferentes de $H_{i,j}$, contradizendo a primeira observação. Ou seja, $V(C_{i,k})\cap V(C_{i,j})\setminus \{v_i\} = \emptyset$.

Para finalizarmos a prova, dois casos devem ser considerados. Se $G[N(v)]$ é um grafo completo, $G[\{v\}\cup N(v)]$ também o é. Contudo, esse é um grafo completo em que todos os vértices têm grau $\Delta(G)$, de modo que, pela conexidade de $G$, devemos ter $G = G[\{v\}\cup N(v)]$, contradizendo a hipótese do enunciado. Se $G[N(v)]$ não é um grafo completo, podemos fixar uma coloração $c$ de $H$ com cores $\{1,2,\dots,\Delta(G)\}$ de modo que $v_1v_2\notin E$, em que $\{v_1,v_2,\dots,v_{\Delta(G)}\}$ é uma enumeração dos vizinhos de $v$ tomada como nas observações acima. Com respeito a essa coloração, considere $u$ o vértice do caminho $C_{1,2}$ que é vizinho de $v_1$. Em particular, sua cor é $2$. Defina agora uma nova coloração $c'$ obtida a partir de $c$ ao trocarmos as cores $1$ e $3$ nos vértices do caminho $C_{1,3}$, de modo que $v_1$ agora se encontra colorido com a cor $3$. Tendo por base a coloração $c'$, sejam $C_{1,2}'$ e $C_{2,3}'$ definidos como nas observações acima. Tem-se então que $u$ é um vértice de $C_{2,3}'$, pois têm cor $2$ e é vizinho de um vértice de cor $3$. Entretanto, ele também pertence a $C_{1,2}'$, dado que o único vértice de $C_{1,2}$ em que as colorações $c$ e $c'$ diferem, pela Observação 3, é o vértice $v_1$. Logo, contradizendo a Observação 3, $c'$ é uma coloração tal que $C_{1,2}'$ e $C_{2,3}'$ são caminhos que se intersectam em um vértice que não é a extremidade comum de ambos. $\square$