Los siete puentes de Königsberg

Durante mucho tiempo, los habitantes de Königsberg, en el siglo XVIII, intentaron resolver un acertijo: por la ciudad pasa el río Pregel, que forma dos islas. Sobre este río hay siete puentes que llevan a las islas. ¿Es posible, en un solo paseo dominical, cruzar todos los puentes, pero cada uno exactamente una vez? Veamos cómo estaban dispuestos los puentes sobre el río:

¿Es posible empezar nuestro paseo en algún lugar y cruzar todos los puentes exactamente una vez? Podemos intentarlo: empezamos abajo a la izquierda y avanzamos hacia arriba y luego, poco a poco, hacia la derecha, así:

Vemos que hemos cruzado seis de los siete puentes y que uno se nos ha quedado sin cruzar. Podemos probar con otro camino…

De nuevo hemos cruzado solo seis de los siete puentes de nuestro Königsberg. Casi parece que no es posible cruzar cada puente exactamente una vez en un solo paseo. Un día, el famoso matemático Leonhard Euler se topó con este problema. Y decir famoso es poco: Euler fue una auténtica leyenda de las matemáticas; en su honor, el número e se llama también número de Euler. Euler se propuso resolver este acertijo. Empezó por marcar las distintas islas o partes de la ciudad a las que llegaban los puentes y de las que salían:

Euler hizo ahora el siguiente razonamiento: si a una isla llega un número par de puentes, podemos cruzar todos esos puentes durante un mismo paseo, empecemos donde empecemos. Sencillamente, por un puente llegamos a la isla y por otro salimos: el número de puentes que quedan por cruzar disminuye en dos. Para poder llegar a la isla por un puente y salir por otro, necesitamos dos puentes. Si a una isla llegan seis puentes, visitaremos la isla tres veces. Por ejemplo, imaginemos que a la isla B llegaran cuatro puentes así:

Entonces, en un solo paseo dominical podemos cruzar todos los puentes, empecemos donde empecemos. ¡Pruébalo! En la figura he marcado un camino. Imaginemos ahora que a la isla B llegara además un puente desde la isla D:

Vemos que el camino que hemos elegido no nos permite cruzar todos los puentes exactamente una vez. Tendríamos que volver a la isla B por algún puente y luego pasar a la isla D. Pero podemos elegir otro camino. Podemos empezar nuestro paseo en la isla B y entonces somos capaces de cruzar todos los puentes exactamente una vez:

Hemos empezado nuestro paseo en la isla B, hemos ido hacia arriba, a la zona A, luego por un puente de vuelta a B, a la zona C, después de nuevo a la isla B y, por último, a la isla D. Así pues, si empezamos en una isla que tiene un número impar de puentes, podemos cruzar todos sus puentes exactamente una vez. O podemos hacerlo justo al revés: empezar en la isla D y terminar en la isla B.

Así, Euler se dio cuenta de que, para poder cruzar todos los puentes exactamente una vez, tiene que cumplirse que todas las islas tengan un número par de puentes o que haya dos islas con un número impar de puentes: en una isla con un número impar de puentes empezamos y en la otra terminamos. Todas las demás islas tienen que tener un número par de puentes. Si miramos los siete puentes originales de Königsberg:

vemos que ¡cada isla tiene un número impar de puentes! La isla A tiene 3, B tiene 5, C tiene 3 y D también tiene 3. Por eso el acertijo no tiene solución: no es posible cruzar los siete puentes exactamente una vez en un solo paseo dominical. Si derribáramos cualquiera de los puentes, de repente el acertijo tendría solución. Derribemos, por ejemplo, uno de los puentes entre las islas B y C:

Vemos que de golpe la isla B tiene 4 puentes y la isla C, dos puentes. A las islas A y D no les ha cambiado el número de puentes. De pronto tenemos dos islas con un número par de puentes y dos islas con un número impar de puentes. Si empezamos nuestro paseo en una de las islas que tienen un número impar de puentes, podemos cruzar todos los puentes exactamente una vez. En la figura hemos empezado en la isla A y hemos terminado en la isla D.

Así, Leonhard Euler resolvió otro famoso problema matemático y, más o menos, sentó las bases de lo que hoy llamamos teoría de grafos, y en su honor un grafo en el que se pueden recorrer todas las aristas exactamente una vez se llama, en el lenguaje de la teoría de grafos, grafo euleriano.