Teorema das 4 cores

Questões-guia:

1. Porque todo grafo planar simples tem pelo menos um vértice com grau até 5?
2. Com base na questão 1, como colorir os vértices de um grafo planar usando no máximo 6 cores?
3. Como fazer para incrementar um pouco este algoritmo, através de contrações, e usar no máximo 5 cores?  Veja dicas no nosso texto auxiliar de Tarjan e colegas (1980).  Cuidado, pois há vários errinhos tipográficos neste texto.  Deve ter sido digitalizado por OCR.
4. O próximo passo seria provar que 4 cores bastam, mas isto ainda é muito difícil.  Vejamos então alguns marcos desta história:

• 1852: O que de Morgan escreveu a Hamilton nesta data?
• 1878: O que Tait provou nesta data?
• 1879: O que Kemper publicou nesta data?
• 1890: O que fez Headwood nesta data?
• 1946: Que contra-exemplo importante surgiu nesta data?
• 1968: O que Grinberg mostrou nesta data?
• 1976: O que Appel e Haken apresentaram nesta data?
• 1986: O que Appel e Haken apresentaram nesta data?
• 1996: O que Robertson, Sanders, Seymour e Thomas apresentaram nesta data?

Exercícios:

1. É verdade que sempre haverá um emparelhamento perfeito no dual de uma triangulação?
2. Ex. 7.3.14 do West.
3. Ex. 7.3.17 do West.