Duas ilhas, duas margens, sete pontes. Contar as pontes por margem dá 3, 3, 3 e 5, e os graus somam 3 + 3 + 3 + 5 = 14 (primeiro link; o terceiro link obtém o mesmo 14 como 3 × 3 + 5, que é o agrupamento mais rápido). A metade desse total é o número de pontes — o segundo link divide e dá 7 — e a relação não é exclusiva deste mapa: cada ponte contribui para duas margens, então os graus têm que ser o dobro do número de arestas. O quarto link, 4 × 3/2 = 6, é o número de pares de massas de terra disponíveis para unir com uma ponte, e há sete pontes para sentar em seis pares, então pelo menos um par de massas de terra está unido por duas pontes em vez de uma.
O argumento de Euler é que um passeio que cruze cada ponte uma vez tem que entrar e sair aos pares de cada massa de terra pela qual passa, então todo vértice usado como ponto de parada tem grau par; só o primeiro e o último vértice do passeio estão isentos, e só há dois. Königsberg tem quatro vértices ímpares, então não existe nenhum passeio do tipo pedido, e a prova está completa antes que alguém meça um rio. Essa é a razão pela qual o artigo é tratado como o primeiro teorema da teoria dos grafos e não como a solução de um passatempo: as distâncias, as formas das margens e as larguras do Pregel são todas irrelevantes, e Euler diz isso, colocando o problema em uma geometria da posição em vez de uma geometria da magnitude. Duas das sete pontes foram destruídas em 1944 e nunca reconstruídas, então hoje a pergunta é de turista; a aritmética aqui é sobre o mapa que enviaram a Euler em 1735.
Resposta
14
Como ler
A soma dos quatro graus. O segundo link a reduz à metade nas sete pontes; o terceiro a soma de outra maneira; o quarto conta os pares de massas de terra.
Fonte
Leonhard Euler, 'Solutio problematis ad geometriam situs pertinentis', 1736, the founding paper of graph theory; the Königsberg bridges on the Pregel were seven in Euler's map, two of which were destroyed in 1944 and not rebuilt
Resolva na calculadora
Estes links abrem a calculadora adequada com os números deste problema já escritos. A linha de cima é o que a tela deveria mostrar: confira você mesmo.