Solucionando o problema das 3 casas através da Teoria do Grafos - FINAL

[veja o problema aqui]

[veja a 1ª parte da solução aqui]

[veja a 2ª parte da solução aqui]

Eis o desfecho da solução:

Se cada região tem no mínimo grau 4 e se há 5 regiões, então a soma dos graus (S_G) será no mínimo 5.4=20, logo o grafo terá no mínimo 10 arestas:

20=2A

2A=20

A=20/2

A=10

 (lembre-se que S_G=2A, ou seja, a soma dos graus é igual ao dobro do número de arestas).

Mas sabemos que o nosso grafo deverá ter 9 arestas, logo o que obtemos foi uma contradição.

Portanto não existe um grafo planar com 6 vértices, 9 arestas e 5 regiões, em outras palavras, o grafo é não planar: as arestas irão se cortar (ou cruzar, ou intersectar ou passar uma por cima da outra).

Então, ainda que você fique a eternidade desenhando jamais vai obter sucesso, pois o problema de construir a figura é insolúvel.

O argumento resumido é este:

Supondo que seja possível, o desenho pretendido deverá ser um grafo planar. Mas se tal grafo existir e for planar, então:

(i) O grafo deverá possuir 6 vértices e 9 arestas e 5 regiões.

(ii) Cada região terá no mínimo grau 4.

(iii) A soma dos graus das faces será igual ao dobro das arestas.

(iv) Como conseqüência de (i) e (ii) concluímos que a soma dos graus será no mínimo 5.4=20.

(v) Como conseqüência de (iii) e (iv) concluímos que o grafo deverá ter pelo menos 10 arestas.

Partimos do princípio de que o grafo deverá ter 9 arestas e fazemos a suposição de ele ser planar. Então concluímos, por meio de procedimentos matemáticos legítimos, que o grafo deverá ter no mínimo 10 arestas, o que evidentemente é uma contradição. Portanto, o único elo fraco da argumentação deve necessariamente ser a suposição de o grafo ser planar, logo o grafo não é planar.

Referência:

LIPSCHUTZ, Seymour; LIPSON, Marc L. Teoria dos Grafos. In: Teoria e Problemas de Matemática Discreta. 2. ed. Porto Alegre: Bookman, 2004. (p.188-228)

*Qualquer crítica ao conteúdo apresentado pode ser feita aqui.

PS: a referência citada contém erros gráficos (assim como edições de outros livros da mesma coleção), contudo é acessível gratuitamente.