Em Kaliningrad (o nome russo para Königsberg), existem duas pontes adicionais além das sete que estavam presentes no século XVIII. Estas novas pontes conectam as regiões
e
e as regiões
e
. Alguém pode cruzar todas as nove pontes em Kaliningrad exatamente uma vez e voltar ao ponto inicial?
Passo 1
O enunciado descreve um grafo com quatro vértices (as regiões
) e nove arestas (pontes). Duas regiões são ilhas (digamos
e
), e as outras duas são margens do rio
e
. As sete pontes originais de Königsberg têm ligações:\r
As duas pontes novas são
e
, totalizando nove arestas. Queremos saber se existe um circuito de Euler (passar por cada aresta exatamente uma vez e voltar ao ponto inicial).
Passo 2
Formamos o grafo com as arestas e contamos o grau de cada vértice. Após as duas pontes novas, as ligações passam a ser:\r
Passo 3
Calculamos o grau de cada vértice somando as arestas incidentes:\r
Passo 4
Pelo teorema de Euler, um grafo conexo admite circuito euleriano se, e somente se, todos os vértices têm grau par. Aqui todos os graus são pares.
Resposta
Sim, existe um percurso que atravessa cada uma das nove pontes exatamente uma vez e retorna ao ponto de partida.