Quantas cores são necessárias para colorir K_{n} ?

Passo 1

O enunciado nos dá o grafo completo K_{n} 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 \chi(G) para um grafo G.

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 k cores, temos uma função de coloração
f: V(G) \to \{1,2,\dots,k\}
tal que para toda aresta uv\in E(G) vale f(u)\neq f(v). O número cromático \chi(G) é o menor k para o qual existe essa coloração própria.

Passo 3

No grafo completo K_{n} 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 n-1 e está ligado a todos os demais. Isso mostra que não é possível usar menos de n cores, ou seja,
\chi(K_{n}) \ge n.

Passo 4

Por outro lado, podemos construir explicitamente uma coloração usando exatamente n cores, atribuindo a cada um dos n 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 n cores.

Resposta

\chi(K_{n}) = n.

Exercícios de Livros Relacionados