Esse e bem legal.Alguem da lista pediu essa informaçao.Da pra demonstrar o teorema de Kuratowsky que diz que os grafos planares tem como menores proibidos o: *K(3,3),que e um grafo bipartido completo tres tres,ou seja,e algo como o troço da agua luz e telefone com as tres casas;e o *K(5)que e o grafo completo cinco,onde ha cinco pessoas em que todos sao amigos de todos.Parece uma estrela dentro de um pentagono. Essa historia de menores o Tengan,o Fabricio e o Shine podem explicar bem melhor do que eu,mas e algo intuitivo como estar contido:um grafo e menor de outro se pode ser obtido pela contraçao e retirada de arestas do primeiro. A demonstracao do K(3,3) e na verdade feita toda vez que um leigo tenta resolver.Pegue as casas C1,C2,C3 e as estaçoes A,L,T. Desenhe sem cruzar as ligaçoes de C1 e C2 com A e L.Voce forma um "quadrilatero" ou ciclo elementar AC1LC2.Veja que tanto faz o C3 estar dentro ou fora.Ao ligar C3 a A e L temos dois ciclos encaixados.Basta dai verificar que tentar colocar o T em qualquer lugar nao da pois alguem fica sem.E fim! Acho que pro K5 deve sair assim mesmo.Mas a volta do teorema e a parte que pega.Deve ter no livro Handbook of Combinatorics.Vouy tentar tirar copias ou comprar o dito.
Ate mais!!!Ass.:Johann Lembre-se: TEA WITH ME THAT I BOOK YOUR FACE ========================================================================= 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 O administrador desta lista é <[EMAIL PROTECTED]> =========================================================================