Re: problema!

["Bruno Woltzenlogel Paleo" <bwp@xxxxxxxxxx>]

> Nos dois casos uma demonstra,c~ao por an'alise cuidadosa de casos 'e
poss'ivel
> mas uma demonstra,c~ao muito mais elegante 'e dada pela f'ormula de Euler
> (V + F = A + 2, onde V, A e F s~ao o n'umero de v'ertices, arestas e faces
> de uma decomposi,c~ao da esfera). Suponha por absurdo que o seu grafo
possa
> ser desenhado em uma esfera. Temos ent~ao para este desenho V + F = A + 2.
> Mas claramente V = 6 e A = 9 donde F = 5. Mas cada face deve ter um
n'umero
> par de lados (pois os v'ertices s~ao alternadamente brancos e pretos),
> donde pelo menos 4 lados. Assim, o n'umero total de lados de faces 'e no
> m'inimo 5*4 = 20. Mas cada aresta 'e contada como lado exatamente duas
vezes
> donde o n'umero de arestas A 'e pelo menos 10, contradizendo A = 9.
> O grafo completo com 5 v'ertices fica agora como exerc'icio.

Como se prova a formula V+F=A+2? O que é uma decomposição da esfera?

<Bruno Woltzenlogel Paleo>