Teorema das 4 cores

Teoria dos Grafos

Jonathan Carvalho Lopes B88886-5
Janderson Lucas de Jesus Freire B928492

Ciências da Computação – CC4P30

Brasília
18 de maio de 2015

Teoria dos Grafos
Teorema das quatro cores

Jonathan Carvalho Lopes B888865
Janderson Lucas de Jesus Freire B928492

Brasília
18 de maio de 2015
Índice
Sumário
Resumo 4
Introdução 5
História do teorema 6
A prova do T4C 8
Mapas e colorações admissíveis 8
Primeiras reações e respostas 14
Conclusão 20
Referencias 21

Resumo

A prova do Teorema das Quatro Cores é a primeira prova de um teorema matemático para a qual o uso de cálculos mecanicamente executados é indispensável. Trata-se basicamente de uma prova por redução ao absurdo, na qual está incluída uma prova por indução matemática cujo passo indutivo requer uma prova com três casos, um dos quais requer mais de mil subcasos. São justamente os cálculos envolvidos na construção desses subcasos, realizados através da execução de um programa, que possibilitam o estabelecimento do lema principal da prova. Um dos tópicos das disputas filosóficas em torno do procedimento diz respeito ao fato de que os cálculos não podem ser realizados por um único ser humano no tempo de uma vida. Tratar-se-ia, assim, de um caso de finitude humanamente não-inspecionável. Esse fato foi destacado como evidência a favor de um suposto caráter experimental do procedimento de prova, naquilo que temos chamado de argumento da introdução da experimentação na matemática. O trabalho apresenta o argumento e sugere algumas distinções conceituais capazes de mitigar suas conclusões através de considerações tecidas desde a perspectiva da filosofia da matemática de Ludwig Wittgenstein.

Introdução

O Problema das Quatro Cores trata da determinação do número mínimo de cores necessárias para colorir um mapa, de países reais ou imaginários, de forma a que países com fronteira