Existe uma demonstração fácil de que 5 cores bastam para pintar um grafo planar. Acho que este é seu problema: tentar provar por absurdo algo que se provaria diretamente. Certamente, se você usa 4 cores para piontar, alguém que tem um estoque de 5,6,7,2002 cores também consegue.
Mas o salto lógico é este: Para que seja preciso 5 cores para pintar o grafo, eu teria que ter 5 nós ligados entre si. Se isto não for corretamente demonstrado, adeus demonstração! Em 17/09/11, Hugo Fernando Marques Fernandes<[email protected]> escreveu: > Olá, Lista. > > Seguinte, estava lendo sobre o "problema das quatro cores", que segundo > entendi é um teorema da teoria dos grafos que afirma que se pode colorir > qualquer grafo planar com quatro cores de modo que nós adjacentes (ou seja, > que possuam aresta ligando-os) não sejam pintados da mesma cor. > > Consta que tal fato permaneceu por séculos sem demonstração, e a que existe > hoje depende de recursos computacionais para ser completada, o que levanta > dúvidas sobre a mesma. > > Minha pergunta então, é a seguinte: > > Para que seja preciso 5 cores para pintar o grafo, eu teria que ter 5 nós > ligados entre si, isto é, eu teria que ter um sub-grafo do meu grafo inicial > que fosse um grafo completo de 5 nós (K5). Ora, sabemos (é fácil demonstrar, > já vi em vários livros a demonstração) que K5 não tem realizações > planares... logo, o teorema segue. > > Sei que isso está errado (afinal de contas, se não estivesse, alguém teria > visto de cara e o problema não teria ficado séculos em aberto...) mas não > consigo ver onde está o erro desse raciocínio. Alguém pode me ajudar? > > Obrigado. > -- /**************************************/ 神が祝福 Torres ========================================================================= Instru��es para entrar na lista, sair da lista e usar a lista em http://www.mat.puc-rio.br/~obmlistas/obm-l.html =========================================================================
