El juego consiste en lo siguiente: ¿Es posible planificar un paseo tal que se crucen todos los puentes sin pasar por ninguno más de una vez?

Algunos de los habitantes de Königsberg opinaban que sí y otros que no.

La investigación que realizó Euler para resolver este problema fue presentada en 1736 en la Academia de Ciencias de San Pesterbusgo. La obra de Euler puede considerarse como el comienzo de la Teoría de Grafos, que forma parte de la Topología, rama de las Matemáticas que Leibniz llamó "geometría de la posición".

Euler, para mayor claridad, sustituyó cada uno de los trozos de tierra firme por un punto y cada puente por un trazo, dando lugar a un esquema simplificado que se representa en la figura adjunta. Así, la isla está representada por el punto al cual llegan cinco trazos, pues son cinco los puentes que van a ella. La figura resultante es un grafo (un grafo es un conjunto de puntos llamados "vértices o nodos" del grafo y un conjunto de lineas que los unen que se llaman "aristas o lados" del grafo).

El problema se reduce a dibujar la figura, partiendo de un punto, de un trazo, es decir, sin levantar el lápiz (boli, pluma...) del papel y sin recorrer una misma línea dos veces. A un recorrido de estas características se le llama camino euleriano.

Demostraremos que es imposible dibujar nuestra figura de un solo trazo. En efecto, a cada punto nodal hay que llegar por un lado y salir por otro distinto; esta regla sólo tiene dos excepciones que son el punto de salida, al cual no hay que llegar y el punto de llegada, del cual no hay que salir.

Por lo tanto, si un tal recorrido fuera posible, es necesario que en todos los vértices del grafo, salvo a lo más en dos, converjan dos, cuatro... aristas, es decir, converja un número par de ellas. 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).

Por lo dicho en el párrafo anterior, si existe un camino euleriano, tenemos dos posibilidades:

• El punto de partida y de llegada es el mismo, entonces en todos los vértices concurre un número par de aristas.
• Los puntos de partida y de llegada son distintos, entonces hay dos vértices con número impar de aristas (el de partida y el de llegada) y todos los demás tienen un número par de aristas.

El recíproco de esta afirmación es también cierto, es decir, si ocurre alguna de las dos posibilidades anteriores, existe un camino euleriano y podríamos realizar la figura correspondiente sin levantar el lápiz del papel y sin pasar dos veces por una misma arista. Además, si todos los nodos tienen un número par de arista se puede empezar por cualquiera de ellos y se terminará, naturalmente, en el que se empezó; y si hay sólo dos con un número impar de aristas, se empieza en uno de ellos y se termina en el otro. La demostraciones formales de estas afirmaciones están fuera del alcance de estas notas.

Después de todo lo comentado se comprenderá por qué la "casita" tiene un camino euleriano y el "sobre" no

Una observación final: no es necesario realizar el grafo, éste se hizo por claridad de la exposición. Podríamos haber contado los puentes que partían de cada trozo de tierra firme y luego haber razonado como lo hizo Euler.