Grafos e RedesMaps

Em 1852, o estudante de botânica Francis Guthrie teve que colorir um mapa dos condados da Inglaterra. Ele observou que quatro cores pareciam suficientes para qualquer mapa que ele tentasse, mas ele não conseguiu encontrar uma prova que funcionasse para todos os mapas. Esse acabou sendo um problema extremamente difícil e ficou conhecido como o teorema das quatro cores. Durante os 100 anos seguintes, muitos matemáticos publicaram "provas" para o teorema das quatro cores, apenas para erros encontrados posteriormente. Algumas dessas provas inválidas foram tão convincentes que levou mais de 10 anos para descobrir erros. Durante muito tempo, os matemáticos foram incapazes de provar que quatro cores são suficientes ou de encontrar um mapa que precisava de mais de quatro cores.