Esta entrada es una continuación de: Königsberg: El problema.
Tras numerosos intentos infructuosos, la solución a este “divertido” problema combinatorio fue proporcionada por el matemático suizo Leonhard Euler en 1736. Euler no solamente demostró la imposibilidad del pretendido paseo, sino que, además, dio un sencillo criterio general para resolver cualquier problema del mismo tipo.
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 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).