Até agora vimos algumas condições necessárias para alta cromaticidade, na forma de limites superiores em $\chi$. Se $\chi (G) \geq k$, por exemplo, então também $\Delta geq k$ (a menos que $G$ seja completo ou um ciclo ímpar), e $G$ tem um subgrafo de grau mínimo em menos $k-1$. Porém, essas condições estão longe de ser suficientes: se $G=K_{n,n}$, digamos, elas valem para todo $k \leq n$, exceto $\chi (G) =2$.

Seria bom também ter algumas condições suficientes para $\chi \geq k$. Se elas forem fáceis de verificar, elas podem fornecer certificados úteis de o por que não conseguimos colorir um determinado grafo com poucas cores. Se eles pudessem ser mostrados como necessários também, eles 'explicariam' por que certos grafos são altamente cromáticos, assim como a condição de casamento no teorema de Hall 'explicaria' por que certos emparelhamentos em grafos bipartidos falham: sua violação claramente impede que um grafo tenha o emparelhamento desejado e é violada toda vez que tal emparelhamento não existe.

Por exemplo, podemos tentar determinar a classe $\mathcal{X} _k$ de grafos $\subseteq$-mínimos que não podem ser coloridos com menos de $k$ cores. Como é fácil verificar (cf. Lema 12.6.1), um dado grafo $G$ satisfaz $\chi (G) \geq k$ se, e somente se, possui um subgrafo em $\mathcal{X}_k$, assim como no teorema da planaridade de Kurotowski com minors ou minors topológicos. Portanto, conter qualquer gráfico de $\mathcal{X} _k$ é um certificado para $\chi \geq k$, e esses certificados juntos 'explicam' esse fenômeno no sentido discutido.

Mas esses certificados serão fáceis de encontrar em um gráfico $k$-cromático arbitrário ou pelo menos fáceis de verificar? Ou seja, será fácil verificar se um determinado grafo $X \in \mathcal{X} _k$ está de fato em $\mathcal{X} _k$, ou apenas que $\chi (X) \geq k$? Voltaremos a esta questão em um momento.

Uma condição óbvia e suficiente para $\chi (G) \geq k$ é que $K^k \subseteq G$. Mas essa condição não é necessária: como o Teorema de Erdós mostrará, os grafos $k$-cromáticos nem precisam conter um triângulo. Portanto, embora $K^k$ certamente esteja em $\mathcal{X} _k$, não é seu único elemento. Reciprocamente, o Lema implica que todos os grafos em $\mathcal{X} _k$ têm grau mínimo pelo menos $k-1$; mas nem todos os grafos de grau mínimo $k-1$ estão em $\mathcal{X}_k$, pois eles não precisam satisfazer $\chi \geq k$.

O seguinte teorema de Erdós implica que $\mathcal{X}_k$ não pode ser finito. De fato, isso implica que para nenhum $k$ existe um conjunto finito $\mathcal{X}$ de grafos $X$ com $\chi (X) \geq 3$ tal que todo grafo $k$-cromático possui um subgrafo em $\mathcal{X}$:

O teorema acima foi provado pela primeira vez de forma não construtiva usando grafos aleatórios, e reproduziremos essa prova mais a frente. Construir gráficos de grande número cromático e circunferência diretamente não é fácil.

A mensagem do teorema de Erdós é que, talvez ao contrário do que esperávamos, um grande número cromático pode ocorrer como um fenômeno puramente global: localmente, em torno de cada vértice, um grafo de grande circunferência se parece com uma árvore e, em particular, é $2$- colorido lá. Mas o que exatamente pode causar alta cromaticidade como um fenômeno glocal permanece um mistério.

No entanto, existe um procedimento simples, embora nem sempre curto, para construir todos os grafos de número cromático pelo menos $k$. Para cada $k \in \mathbb{N}$, vamos definir a classe de grafos $k$-construtíveis recursivamente da seguinte forma:

$(i)$ $K^k$ é $k$-contrutível;

$(ii)$ Se $G$ é $k$-construtível e dois vértices $x,y$ de $G$ não são adjacentes, então $(G+xy)/xy$ também é $k$-construtível.

$(iii)$ Se $G_1,G_2$ são $k$-construtíveis e existem vértices $x,y_1,y_2$ tais que $G_1 \cap G_2 = \{x\}$ e $xy_1 \in E(G_1)$ e $xy_2 \in E(G_2)$, então $(G_1 \cap G_2)-xy_1-xy_2 +y_1y_2$ também é $k$-construtível.

Pode-se facilmente verificar indutivamente que todos os grafos $k$-construtíveis e, portanto, seus supergrafos, são pelo menos $k$-cromáticos. Por exemplo, qualquer coloração do grafo $(G+xy)/xy$ em $(ii)$ induz uma coloração de $G$ e, portanto, por suposição indutiva, usa pelo menos $k$ cores. Da mesma forma, em qualquer coloração do grafo construído em $(iii)$, os vértices $y_1$ e $y_2$ não têm ambos a mesma cor que $x$, então esta coloração induz uma coloração de $G_1$ ou $G_2$ e, portanto, usa pelo menos $k$ cores.

É notável, porém, que o inverso também seja válido:

O teorema de Hajós resolve nosso problema do tipo Kuratowski para grafos altamente cromáticos, que era encontrar uma classe de grafos de número cromático pelo menos $k$ com a propriedade de que todo grafo tem subgrafo nessa classe? Formalmente, sim, embora com uma classe de caracterização infinita (a classe de grafos K-construtíveis) que contém $\mathcal{X}_k$ adequadamente. Ao contrário da caracterização de grafos planares de Kuratowski, no entanto, isso não torna, pelo menos não obviamente, o teorema de Hajó uma boa caracterização dos grafos do número cromático $<k$: como se pode mostrar, provando que um determinado grafo $k$-construtível é de fato $k$-construtível é tão difícil quanto provar que um gráfico de número cromático $\geq k$ realmente precisa de pelo menos $k$ cores. Consulte a nota para obter detalhes.*