1. **Enunciado do problema:** Eugénia quer percorrer todas as divisões da mansão passando por cada porta exatamente uma vez e terminando na divisão onde começou. 2. **Modelagem do problema:** Representamos as divisões como vértices e as portas como arestas de um grafo. 3. **Construção do grafo:** - Vértices: M, N, O, P, Q, R, S, T - Arestas (portas) conforme o esquema: - M-N, N-O - M-P, N-Q, O-T - P-Q - P-R, Q-S - R-S, S-T 4. **Verificação da existência de um ciclo euleriano:** - Um ciclo euleriano existe se e somente se o grafo for conexo e todos os vértices tiverem grau par. 5. **Graus dos vértices:** - M: 2 (N, P) - N: 3 (M, O, Q) - O: 2 (N, T) - P: 3 (M, Q, R) - Q: 3 (N, P, S) - R: 2 (P, S) - S: 3 (Q, R, T) - T: 2 (O, S) 6. **Análise dos graus:** - Vértices com grau ímpar: N, P, Q, S (4 vértices) 7. **Conclusão:** - Como existem 4 vértices de grau ímpar, não existe ciclo euleriano. - Para existir um caminho euleriano que comece e termine no mesmo vértice, todos os graus devem ser pares. 8. **Solução para tornar possível:** - Devemos adicionar portas para tornar os graus pares. - Como há 4 vértices ímpares, o número mínimo de portas a adicionar é $\frac{4}{2} = 2$. - Podemos conectar pares de vértices ímpares, por exemplo: - Adicionar porta entre N e S - Adicionar porta entre P e Q 9. **Verificação após adição:** - Graus após adicionar N-S e P-Q: - N: 4 (M, O, Q, S) - P: 4 (M, Q, R, Q) (note que P-Q já existe, então devemos escolher outra aresta, por exemplo P-S) 10. **Ajuste final:** - Adicionar portas entre N-S e P-S para corrigir os graus. **Resposta final:** - a) Não, Eugénia não consegue percorrer todas as portas uma única vez e voltar ao início com o grafo atual. - b) São necessárias 2 portas adicionais, por exemplo entre N e S e entre P e S, para que todos os vértices tenham grau par e o percurso seja possível.