Neste trabalho estudamos um pouco de Teoria dos Grafos, abordando diversas definições e teoremas interessantes. Apresentamos o Teorema das Quatro Cores, desde o surgimento do problema com Francis Guthrie. Analisamos a demonstração do teorema realizada por Alfred Bray Kempe e sua refutação através do contraexemplo de Percy John Heawood. Analisamos também a demonstração do Teorema das Cinco Cores de Percy John Heawood. Porém, apresentamos a primeira demonstração válida do Teorema das Quatro Cores, como sua particularidade de ter sido feita com o auxílio de um computador. O trabalho é concluído com uma análise sobre os benefícios que o conhecimento de Teoria dos Grafos pode render aos alunos do Ensino Básico, e como professor o pode trabalhar este assunto em sala de aula, inclusive abordando o problema de coloração de mapas. / In this paper we study Graph Theory, addressing various definitions and interesting theorems. We present the Four Color Theorem, since the origin of the problem with Francis Guthrie. We analyze the proof of the theorem presented by Alfred Bray Kempe, and its refutation by Percy John Heawood counter-example. We also analyze the Percy John Heawood demonstration of the Five Color Theorem. Finally, we present the first valid proof of the Four Colors Theorem, with its peculiarity of having been done with the aid of a computer. We conclude with an analysis of the beneficial that the knowledge of Graph Theory can render students of Basic Education, and how a teacher can work this topic in the classroom, including addressing the problem of map coloring.

Coordenação de Aperfeiçoamento de Pessoal de Nível Superior - CAPES / This work brings an approach to the basic notions of Graph Theory, presenting historical context, concepts, de nitions and examples in order to provide the reader with previous knowledge of the theory. The main objective is to perform a study of the graphs applied to the staining using the dual graph and the method of the greedy algorithm. To do so, we will present the demonstration attempt of the 4-Color Theorem that had been developed by Kempe and the proof of the 5-Color Theorem, made 11 years later by Heawood. Finally, we will seek the resolution of some situations problems that will be modeled through the coloring of vertices. / Este trabalho traz uma abordagem às noções da Teoria dos Grafos, apresentando contexto histórico, conceitos, definições e exemplos com o intuito de proporcionar ao leitor conhecimentos prévios da teoria. O principal objetivo é efetuar um estudo dos grafos aplicados à coloração mediante o uso do grafo dual e o métdo do algoritmo guloso. Para tanto, executaremos um esboço acerca da tentativa de demonstração do Teorema das 4 Cores que fora desenvolvida por Kempe e da prova do Teorema das 5 Cores, feita 11 anos mais tarde por Heawood. Por fim, buscaremos a resolução de algumas situações problemas que serão modeladas através da coloração de vértices. / São Cristóvão, SE

Neste trabalho estudamos um pouco de Teoria dos Grafos, abordando diversas definições e teoremas interessantes. Apresentamos o Teorema das Quatro Cores, desde o surgimento do problema com Francis Guthrie. Analisamos a demonstração do teorema realizada por Alfred Bray Kempe e sua refutação através do contraexemplo de Percy John Heawood. Analisamos também a demonstração do Teorema das Cinco Cores de Percy John Heawood. Porém, apresentamos a primeira demonstração válida do Teorema das Quatro Cores, como sua particularidade de ter sido feita com o auxílio de um computador. O trabalho é concluído com uma análise sobre os benefícios que o conhecimento de Teoria dos Grafos pode render aos alunos do Ensino Básico, e como professor o pode trabalhar este assunto em sala de aula, inclusive abordando o problema de coloração de mapas. / In this paper we study Graph Theory, addressing various definitions and interesting theorems. We present the Four Color Theorem, since the origin of the problem with Francis Guthrie. We analyze the proof of the theorem presented by Alfred Bray Kempe, and its refutation by Percy John Heawood counter-example. We also analyze the Percy John Heawood demonstration of the Five Color Theorem. Finally, we present the first valid proof of the Four Colors Theorem, with its peculiarity of having been done with the aid of a computer. We conclude with an analysis of the beneficial that the knowledge of Graph Theory can render students of Basic Education, and how a teacher can work this topic in the classroom, including addressing the problem of map coloring.