Los puentes de Königsberg

No existe ningún paseo que recorra todos los puentes una y sólo una vez.

Leonard Euler, para solucionar este problema y otros similares ideó una forma de representación simplificada mediante líneas y puntos y generó sobre ellas una teoría conocida como teoría de grafos. A la derecha, abajo, puede verse el grafo que corresponde a los puntes de Königsberg, en el que los puntos representan las porciones de tierra y las líneas representan los puentes.

En cuanto a la solución del problema propuesto, resumiendo los razonamientos de Euler, podemos decir que para trazar una ruta que recorra todas las líneas, cada punto debe estar unido a un número par de líneas (de cada par, una línea sería para entrar y otra para salir) porque si es impar habremos de salir, forzosamente, por una de las líneas ya recorridas. Las únicas excepciones posibles son los dos puntos que corresponden al inicio y al final del recorrido.

En este caso, tenemos cuatro puntos y todos ellos están unidos a un número impar de líneas, por lo que el paseo deseado es imposible.