Questão 67023

Em uma aula de Lógica e Matemática Discreta, um professor quer demonstrar a aplicação da teoria dos grafos para modelar e resolver problemas do mundo real. Ele escolhe o problema das 'Sete Pontes de Königsberg', um problema histórico que deu origem à teoria dos grafos com Leonhard Euler. Ele apresenta o problema: "A cidade de Königsberg era cortada por um rio, com duas ilhas no meio, conectadas entre si e com as margens por sete pontes. A questão era: é possível fazer um passeio pela cidade que cruze cada uma das sete pontes exatamente uma vez e retorne ao ponto de partida?" Ele então cita um trecho de um livro de história da matemática: "Euler resolveu o problema de forma genial ao abstrair a situação. Ele representou cada uma das quatro massas de terra (as duas margens e as duas ilhas) como um vértice (ou nó) e cada ponte como uma aresta conectando os vértices correspondentes. O problema então se transformou em: é possível encontrar um 'caminho euleriano' (que passa por todas as arestas uma vez) ou um 'circuito euleriano' (um caminho euleriano que começa e termina no mesmo vértice) neste multigrafo? Euler provou que um grafo conectado tem um circuito euleriano se, e somente se, todo vértice tiver grau par (um número par de arestas incidindo sobre ele)." O professor desenha o grafo correspondente ao mapa de Königsberg, que possui 4 vértices com os seguintes graus: 3, 3, 3 e 5.

Com base na abstração de Euler e em seu teorema, qual é a solução para o problema das Sete Pontes de Königsberg?