Proposição

Um grafo $G$ com $m$ arestas satisfaz

$$k= \chi(G) \leq \frac{1}{2} + \sqrt{2m + \frac{1}{4}}$$

onde:

• $\chi(G)$ é a número cromático (vertice) de $G$.

Demonstração: Seja $\mathcal{c}$ uma coloração de vértice de $G$ com $k=\chi(G)$ cores. Então $G$ tem pelo menos uma aresta entre quaisquer duas classes de cores: caso contrário, poderíamos ter usado a mesma cor para ambas as classes.

Se, por exemplo, temos $1,2$ e $3$ componentes conexas como na imagem a seguir:

Vemos que a situação é uma $3$-coloração, contudo se não existisse a aresta $1-2$, então poderíamos trocar a cor do $2$ para a cor do $1$, ou vice versa, tendo assim uma $2$-coloração.

Dessa forma o número de arestas $m$ de um grafo $G$, possui a seguinte relação:

$$m \geq \binom{k}{2} = \frac{k(k-1)}{2}$$

Assim, resolvendo para $k$, podemos calcular a raiz da equação:

$$k \leq \frac{1}{2} + \sqrt{2m + \frac{1}{4}}$$

$\square$