O GRAFO DE PETERSEN

"...it continues to be a yardstick with which to measure conjectures."
D. A. Holton & J. Sheehan em "The Petersen Graph"

Primeiramente, o que é um grafo?

Um grafo G consiste de um conjunto finito V, de elementos chamados vértices, e um conjunto finito A, de elementos chamados arestas, tal que A está contido no conjunto de pares não ordenados de V. Por exemplo, o grafo de Petersen, que a partir de agora denominaremos P, é definido como 

V = {1, 2, 3, 4, 5, 1', 2', 3', 4', 5'}

A={1-2, 2-3, 3-4, 4-5, 5-1, 1-1', 2-2', 3-3', 4-4', 5-5', 1'-3', 2'-4', 3'-5', 4'-1', 5'-2'}

Veja que a definição não diz nada sobre como deve ser o desenho do grafo, por exemplo, P pode ser representado de várias outras maneiras: 





Antes de falarmos mais sobre P, precisamos falar um pouco de um dos principais problemas da Teoria dos Grafos.

Teorema das Quatro Cores

Em 1852, Francis Guthrie, enquanto tentava pintar um mapa dos condados da Inglaterra, percebeu que quatro cores eram suficientes. Perguntou, então, ao seu irmão Frederick se era sempre verdade que qualquer mapa pode ser colorido com quatro cores de modo que regiões adjacentes (isto é, aquelas com uma fronteira comum, não apenas um ponto) tivessem cores distintas.

Mas por que esse é um problema da Teoria dos Grafos? 

Tomamos a capital de cada país (na verdade, podemos tomar um ponto arbitrário dentro dele) e ligamos as capitais de países vizinhos. Obtemos, assim, um grafo plano, ou seja, é possível desenhá-lo de modo que as suas arestas cruzem-se apenas nos vértices. 

Desse modo, o problema torna-se mostrar que todo grafo plano pode ter seus vértices pintados com 4 cores de modo que vértices ligados por uma aresta tenham cores diferentes (a partir de agora, iremos nos referir a esse problema como 4CT). 

Frederick Guthrie comunicou a conjectura para um de seus professores, o matemático Augustus De Morgan, que a contou em uma carta para outro cientista, Sir William Hamilton. Enfim, um ano mais tarde, Kempe apresentou a primeira ``demonstração'', cujo erro foi descoberto por Heawood em 1864 (onze anos depois!). 

Em 1880, Tait publica outra demonstração, e é aí que começa a história de P. Porém o leitor terá que esperar ainda um pouquinho, pois necessitamos de algumas definições:

Surgimento de P

No artigo de 1880, Tait prova que 4CT é equivalente a:

Todo grafo plano cúbico sem arestas de corte pode ter suas arestas pintadas com três cores de tal maneira que em cada um dos vértices incidam arestas das três cores.
Então, supondo que todo grafo satisfazendo essas hipóteses é hamiltoniano, ele conseguiu concluir sua "demonstração" de 4CT. 

Julius Petersen, matemático dinamarquês (1839 - 1910), aparentemente não ficou muito convencido com a prova de Tait e apresentou um exemplo de um grafo cúbico sem arestas de corte, mas não hamiltoniano. Surgia o Grafo de Petersen.

Contudo isso ainda não mostrava que a demonstração era incorreta, pois o grafo de Petersen não é plano. Apenas em 1946, Tutte conseguiu um grafo plano com tais características: 

O grafo de Petersen começava nesse momento a mostrar sua importância como padrão de comparação na verificação de conjecturas, como diz a citação no início desse artigo. 

E, afinal de contas, 4CT foi provado? Sim, em dois artigos de 1977 por Kenneth Appel e Wolfgang Haken (o segundo artigo com a participação de John Koch). Porém a demonstração fez uso de mais de 1200 horas de processamento (isso mesmo, computador) o que provocou grandes discussões sobre se o problema estava realmente resolvido, já que é praticamente impossível verificar se o trabalho feito pelo computador estava certo (de fato, vários erros foram encontrados, corrigidos pelos autores em 1989 - só os encontrados, é claro). 

Recentemente, Robertson, Sanders, Seymour e Thomas encontraram uma resolução mais simples, mas ainda dependente do auxílio de computadores. Só que agora algumas (quem sabe, várias) horas em um PC bastam. Veja em http://www.math.gatech.edu/~thomas/FC/ftpinfo.html.

P, finalmente

Historicamente, as propriedades importantes de P são: não é hamiltoniano, nem plano, nem suas arestas podem se pintadas com três cores de modo que em cada vértice incidam as 3 cores. Ficam então como desafio as demonstrações dessas (não) propriedades. E algumas dicas: 

Não hamiltoniano: Pinte os vértices 1, 2, 3, 4, 5 de verde e os vértices 1', 2', 3', 4', 5' de amarelo. Considere as arestas verde-verde, verde-amarelo e amarelo-amarelo. Suponha que P seja hamiltoniano. Por quantas de cada tipo tal caminho passaria?

Não plano: Para grafos planos vale a Fórmula de Euler: V - A + F = 2, onde V: número de vértices, A: arestas e F: faces, como nos sólidos geométricos. Atenção! Uma das faces, a de fora, é infinita. Mostre que essa relação não pode valer para P.

Suas arestas não podem ser pintadas com três cores...: Suponha que seja possível tal pintura. Observe quais são as cores que ligam as arestas do pentágono "de fora" ao "de dentro". O primeiro desenho apresentado para P (aquele com os dois pentágonos) agora fará sentido. 

Envie seus comentários e resoluções (há 3 problemas aqui em cima) para info@opm.mat.br.

Referências