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 B e C e as regiões B e D. 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 A,B,C,D) e nove arestas (pontes). Duas regiões são ilhas (digamos A e B), e as outras duas são margens do rio C e D. As sete pontes originais de Königsberg têm ligações:\r
A\!-\!C:2,\quad A\!-\!B:1,\quad A\!-\!D:1,\quad B\!-\!C:1,\quad B\!-\!D:2.\r
As duas pontes novas são B\!-\!C e B\!-\!D, 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
A\!-\!C:2,\quad A\!-\!B:1,\quad A\!-\!D:1,\quad B\!-\!C:1+1=2,\quad B\!-\!D:2+1=3.

Passo 3

Calculamos o grau de cada vértice somando as arestas incidentes:\r
\deg(A)=2+1+1=4,\quad \deg(B)=1+2+3=6,\quad \deg\text{(C)}=2+2=4,\quad \deg(D)=1+3=4.

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.