Fórum de Matemática
DÚVIDAS? Nós respondemos!

alguém me pode ajudar neste exercício se faz favor, estou com alguma duvida(a imagem do grafo esta em anexo)

(a) Considere o labirinto da figura Comece por representar o labirinto por um grafo.

Indique todos os caminhos de Euler possıveis entre o centro A do labirinto e a saıda
L.
(b) E possıvel construir um grafo planar, simples, bipartido com 8 vertices e 13 arestas?

Para cumprir as regras do forum vou só responder a uma questão (a alínea b) até porque a alínea a é 99,9% de suor 0,1% de inspiração.

Para a alínea b lembre-se que se um grafo é planar então também é desenhável na esfera e terá de obedecer à fórmula de Euler V-A+F=2 onde V é o nº de vértices, A é o nº de arestas e F é o nº de faces. Logo um tal grafo com 8 vértices e 13 arestas terá de ter 7 faces. Sendo um grafo bipartido (e simples) estas faces terão de ter um nº par de arestas adjacentes maior ou igual a 4. Como cada aresta é adjacente a duas faces temos que a soma, sobre todas as faces, das arestas adjacentes será 26 que é duas vezes o nº de arestas do grafo. Mas se cada uma das 7 faces tem pelo menos 4 arestas adjacentes temos que a soma teria de ser pelo menos 4x7=28 o que é uma contradição. Logo tal grafo não pode ser planar.