Como verificamos através da aplicação de um algoritmo guloso, todo grafo $G = (V,E)$ admite uma coloração de seus vértices com $\Delta(G)$ $+1$ cores. Em alguns cenários, essa quantidade de fato se faz necessária, conforme explicado pelos seguintes itens:
Curiosamente, porém, as duas situações acima são as únicas que exigem uma cor a mais do que o grau máximo de seus grafos:
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
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$