Um círculo foi dividido em
setores. De quantos modos podemos colori-los, cada setor com uma só cor, se dispomos de
cores diferentes e setores adjacentes não devem ter a mesma cor?
Passo 1
O enunciado pede o número de colorações próprias de um círculo dividido em
setores, usando
cores
, de modo que setores adjacentes nunca tenham a mesma cor. Podemos modelar isso como o problema de colorir o grafo ciclo
com
cores, sem arestas bichromáticas.
Passo 2
Se tirássemos a aresta que liga o setor
de volta ao setor
, obteríamos um caminho de
vértices. Nesse caso, para colorir o caminho de forma que cada vértice difira do anterior basta:
— escolher a cor do primeiro vértice de maneiras;
— para cada um dos vértices seguintes, escolher qualquer das
cores diferentes da cor do vértice imediatamente anterior.
Logo, o número de colorações desse caminho é
— escolher a cor do primeiro vértice de
— para cada um dos
Logo, o número de colorações desse caminho é
Passo 3
Para fechar o ciclo precisamos ainda impor que o setor
tenha cor diferente do setor
. O polinômio cromático de
(grafo ciclo com
vértices) é um resultado clássico e vale
Ele já incorpora tanto as restrições de adjacência sequencial quanto a restrição adicional entre os vértices 1 e
.