Olá, Pessoal! Pelo menos quatro cores são necessárias para se resolver o problema geral de colorir um mapa. Como ninguém conseguiu produzir um mapa que necessitasse de mais de quatro cores, foi formulada uma conjectura de que quatro cores são, de fato, suficientes. Essa conjectura ficou conhecida como o problema das quatro cores. Ele foi proposto, pela primeira vez, ao matemático Augustus De Morgan por um de seus alunos em 1852 e recebeu, mais tarde, bastante atenção. Permaneceu sem demonstração, no entanto, por mais de 100 anos. Em 1976, dois matemáticos da Universidade de Illinois, Wolfgang Haken e Kenneth Appel, usaram um computador para analisar um grande número de casos em uma demonstração por absurdo, verificando, assim, a conjectura das quatro cores.
O problema das cinco cores diz que o número cromático de um grafo planar simples e convexo é, no máximo, 5. Enquanto o teorema das quatro cores é muito difícil de provar, o teorema das cinco cores pode ser provado por indução no número de nós do grafo. O problema das seis cores pode ser provado como um problema de colorir um mapa sem usar o grafo dual. A propósito, prove que, em qualquer árvore com n nós, o número total de extremidades de arcos é 2n - 2. Abraços! ______________________________________________ WebMail UNIFOR - http://www.unifor.br. ========================================================================= Instruções para entrar na lista, sair da lista e usar a lista em http://www.mat.puc-rio.br/~nicolau/olimp/obm-l.html =========================================================================