El problema de los puentes de Königsberg.

El río Pregel, cruzaba Königsberg (actualmente Kaliningrado, Rusia) y dividía la ciudad en dos partes (A, B) y dos islas (C, D) todo ello, comunicado por siete puentes.


El problema consistía en empezar por un puente, pasar por los otros seis puentes restantes sin repetir ninguno, y volver al puente de partida.

Problema que podéis comprobar que es imposible de resolver.

Demostración de Euler:


En 1736, Euler, presentó en la Academia de Ciencias de San Petersburgo una demostración sobre el problema.

En dicha demostración, Euler, sustituyó cada una de las partes de la ciudad por un punto y cada puente por un trazo, dando lugar a la siguiente imagen:




La demostración que planteó Euler se reduce a dibujar la figura, sin levantar el lápiz del papel y sin recorrer una misma línea dos veces. A un recorrido de estas características se le llama camino euleriano.

Por tanto, si tal recorrido fuera posible, es decir, poder dibujar la figura sin levantar el lápiz, es necesario que en todos los vértices del grafo, converja un número par de ellas (salvo en el punto de entrada o salida si son diferentes). Pero en cada uno de los nodos del grafo correspondiente a los puentes de Königsberg concurre un número impar de aristas (3, 5, 3, 3). Con lo cual, Euler logró demostrar que es imposible resolver el problema de los puentes de Königsberg.