Colorindo grafos planos com restrições de cor de arestas

Professor Henrique A.

Identidade verificada

• CPF verificado
• E-mail verificado

Respondeu há 1 ano

Vamos começar observando que um grafo planar com 8 vértices, cada um com grau 5, tem 24 arestas. Isso ocorre porque a soma dos graus de todos os vértices é igual a duas vezes o número de arestas (pelo Teorema do Aperto de Mão), e nesse caso temos:

8 x 5 = 40
40 / 2 = 20
O grafo tem 24 arestas.

Agora, para contar o número de colorações possíveis, vamos usar o Princípio da Inclusão-Exclusão. Seja Fi o evento de que a face i do grafo tenha todas as suas arestas da mesma cor. Queremos contar o número de colorações que não satisfazem nenhum desses eventos Fi.

O número total de colorações possíveis é 4^24, já que cada aresta pode ser colorida com uma das quatro cores. Para contar o número de colorações que satisfazem pelo menos um dos eventos Fi, vamos usar o Princípio da Inclusão-Exclusão. Temos:

|F1 U F2 U ... U Fk| = ?|Fi| - ?|Fi ? Fj| + ?|Fi ? Fj ? Fk| - ... + (-1)^(k-1) |Fi ? Fj ? ... ? Fk|

Onde k é o número de faces do grafo. Observe que o valor de k depende das colorações escolhidas, pois uma face pode ter todas as suas arestas de uma determinada cor em uma coloração e de outra cor em outra coloração. No pior caso, temos que k é igual ao número total de colorações possíveis, ou seja, k = 4^24.

Agora precisamos calcular o valor de cada um dos termos acima. Para o primeiro termo, temos:

?|Fi| = k x 4 = 4^(24+1)

Isso ocorre porque cada face pode ser colorida com uma das quatro cores, e há k faces.

Para o segundo termo, temos:

?|Fi ? Fj| = (k escolhe 2) x 3 x 4^(24-2)

Isso ocorre porque escolhemos duas faces para terem todas as suas arestas da mesma cor (existem k escolhe 2 pares de faces distintas), depois escolhemos uma cor para essas arestas (existem 3 cores restantes) e finalmente escolhemos as cores das demais arestas (existem 4^(24-2) maneiras de fazer isso).

Para o terceiro termo, temos:

?|Fi ? Fj ? Fk| = (k escolhe 3) x 2 x 3 x 4^(24-3)

Isso ocorre porque escolhemos três faces para terem todas as suas arestas da mesma cor (existem k escolhe 3 trios de faces distintas), depois escolhemos duas cores para essas arestas (existem 2 cores restantes) e finalmente escolhemos as cores das demais arestas (existem 4^(24-3) maneiras de fazer isso).

Continuando dessa forma, podemos calcular todos os termos da fórmula. O último termo é:

(-1)