Los puentes de Königsberg

Königsberg (actualmente Kaliningrado, Rusia) era una ciudad de Prusia del siglo XVIII. El problema tiene como protagonista a un río, el río Pregel, que cruzaba la ciudad, a dos islas que se encontraban en el mismo y a siete puentes que comunicaban las dos partes de la ciudad con las mismas. Concretamente la situación era como se describe en la imagen ( y  son las dos partes de la ciudad y  y  las dos islas):

La respuesta es negativa, es decir, no existe una ruta con estas características. El problema puede resolverse aplicando un método de fuerza bruta, lo que implica probar todos los posibles recorridos existentes. Sin embargo, Euler, en 1736, en su publicación «Solutio problematis ad geometriam situs pertinentis»,1​ demuestra una solución generalizada del problema, que puede aplicarse a cualquier territorio en el que ciertos accesos estén restringidos a ciertas conexiones, como el de los puentes de Königsberg. Para dicha demostración, Euler recurre a una abstracción del mapa y se enfoca exclusivamente en las regiones terrestres y las conexiones entre ellas. Cada puente quedó representado mediante una línea que unía a dos puntos, y cada uno de estos puntos representaba una región diferente. Así, el problema se reduce a decidir si existe o no un camino que comience por uno de los puntos, recorra todas las líneas una sola vez y regrese al mismo punto de partida.

Euler determinó, en el contexto del problema, que los puntos intermedios de un recorrido posible necesariamente han de estar conectados a un número par de líneas. En efecto, si llegamos a un punto desde alguna línea, entonces el único modo de salir de ese punto es por una línea diferente. Esto significa que tanto el punto inicial como el final serían los únicos que podrían estar conectados con un número impar de líneas. Sin embargo, el requisito adicional del problema dice que el punto inicial debe ser igual al final, por lo que no podría existir ningún punto conectado con un número impar de líneas.