Quantas cores são necessárias para colorir
?
Passo 1
O enunciado nos dá o grafo completo
e pede o número mínimo de cores para uma coloração própria de vértices. O conteúdo envolvido é teoria de grafos, mais especificamente o conceito de número cromático, que denotamos por
para um grafo
.
Passo 2
Uma coloração própria de vértices é uma atribuição de cores a cada vértice de forma que vértices adjacentes tenham cores diferentes. Formalmente, se usamos
cores, temos uma função de coloração
tal que para toda aresta
vale
. O número cromático
é o menor
para o qual existe essa coloração própria.
Passo 3
No grafo completo
todo par de vértices é adjacente. Logo, cada vértice deve receber uma cor distinta de todas as outras, pois todo vértice tem grau
e está ligado a todos os demais. Isso mostra que não é possível usar menos de
cores, ou seja,
Passo 4
Por outro lado, podemos construir explicitamente uma coloração usando exatamente
cores, atribuindo a cada um dos
vértices uma cor diferente. Como não existem restrições além de não repetir cor em vértices adjacentes, isso é válido e usa
cores.