¿Se pueden recorrer sin repetir ninguna las seis carreteras que unen cuatro pueblos?

1. Con cuatro pueblos unidos de dos en dos hacen falta seis carreteras

Llama a los pueblos A, B, C y D. Desde cada uno salen carreteras hacia los otros tres, así que 3 carreteras por pueblo, 4 pueblos: 12. Pero la carretera de A a B es la misma que la de B a A, y la hemos contado dos veces, una desde cada extremo. Al dividir entre 2 salen 6 carreteras.

El mismo razonamiento sirve para cualquier número n de pueblos: cada uno tiene n − 1 carreteras, y el total es n(n − 1)/2. Con 5 pueblos son 10 carreteras; con 6, 15. En matemáticas, a un dibujo de puntos y líneas se le llama grafo; los puntos son los vértices, las líneas son las aristas, y el número de líneas que llegan a un vértice es su grado. En nuestro dibujo, los cuatro vértices tienen grado 3. Un grafo en el que cada punto está unido con todos los demás se llama grafo completo[2].

2. Se puede recorrer todo sin repetir solo si hay 0 o 2 pueblos con un número impar de carreteras

Prueba con el dedo: intenta pasar por las seis carreteras sin repetir ninguna: no lo conseguirás, siempre te sobra una. No es mala suerte. En matemáticas, un recorrido que usa cada línea exactamente una vez se llama camino euleriano, y si además termina donde empezó, ciclo euleriano. Existe cuando el dibujo está formado por una sola pieza y hay 0 o 2 puntos de grado impar: con 2, el recorrido empieza en uno de ellos y termina en el otro; con 0, empieza y termina en el mismo sitio[2].

En el dibujo de los cuatro pueblos, los cuatro vértices tienen grado 3, que es impar. Hay cuatro puntos impares, y 4 no es ni 0 ni 2. Respuesta: no se puede. Y no hace falta ningún mapa más fino: la longitud de las carreteras y su forma no importan, solo cuántas llegan a cada pueblo.

Esta es la respuesta a la pregunta del título. Lo que queda es entender por qué la regla funciona, de dónde viene y qué cambia si cambias el dibujo.

3. Euler aplicó la misma idea a los siete puentes de Königsberg

Königsberg era una ciudad de Prusia Oriental, hoy Kaliningrado, en Rusia. El río Pregel la dividía en cuatro zonas de tierra, unidas por siete puentes. Se cuenta que los vecinos se preguntaban si era posible dar un paseo cruzando cada puente una sola vez[2][3].

Euler se dio cuenta de que la forma de las islas y la longitud de los puentes eran lo de menos. Lo único que importaba era qué zona se unía con cuál y por cuántos puentes. Sustituyó cada zona por un punto y cada puente por una línea. Su trabajo se titula «Solutio problematis ad geometriam situs pertinentis» («Solución de un problema relativo a la geometría de posición»), está escrito en 1735 y se publicó en 1741 en las actas de la Academia de San Petersburgo; el archivo que reúne sus obras lo describe como uno de sus trabajos más famosos y suele citarse como el primero de la topología y de la teoría de grafos[1]. Algunas fuentes dan 1736 como año de la solución; aquí seguimos al archivo de Euler y a la revista SUMA, que hablan de 1735[3].

En este dibujo, a un punto llegan cinco líneas y a los otros tres, tres cada uno: los cuatro son impares. Es exactamente la situación de los cuatro pueblos unidos de dos en dos, por lo que tampoco aquí hay paseo posible[2]. Dos problemas que sobre el mapa no se parecen en nada resultan ser el mismo dibujo. A mí, esa es la parte más sorprendente: quedarse solo con «qué se une con qué» y olvidar la forma convierte problemas distintos en uno solo.

4. Por qué un punto por el que se pasa de largo tiene que tener un número par de caminos

Piensa en un pueblo por el que atraviesas a mitad del recorrido. Entras por una carretera y sales por otra: cada paso gasta dos. Si todas las carreteras del pueblo se usan exactamente una vez, el total de carreteras de ese pueblo se agrupa de dos en dos, y por tanto es par[4].

Hay solo dos excepciones: el pueblo donde empiezas, donde la primera carretera es de salida y sobra una (puede ser impar), y el pueblo donde terminas, donde la última es de entrada. Por eso, como mucho, puede haber dos pueblos impares. Y si sales y terminas en el mismo pueblo, todos son pares[4][2].

Hay además un detalle curioso: el número de puntos impares siempre es par. Si sumas los grados de todos los puntos, cada línea se cuenta dos veces (una por cada extremo), y el resultado es el doble del número de líneas, o sea, par. Por eso no puede existir un dibujo con exactamente 1 o 3 puntos impares.

Todo lo anterior demuestra que la condición es necesaria. ¿Basta con ella? Es decir, si el dibujo es de una sola pieza y tiene 0 o 2 puntos impares, ¿siempre se puede recorrer? Sí, pero Euler enunció que la condición también basta sin demostrarlo. Según Wikipedia, la primera demostración completa la publicó el matemático alemán Carl Hierholzer en 1873, de forma póstuma (Hierholzer ya había muerto)[2]. Es una fecha que no hemos podido comprobar en el artículo original.

5. Con cinco pueblos unidos de dos en dos sí se puede, y con seis vuelve a ser imposible

Volvamos a los cuatro pueblos. Si quitas una sola carretera, la de A a B, los grados cambian: A y B pasan a tener 2, y C y D se quedan con 3. Quedan dos puntos impares, así que ahora sí hay recorrido: empieza en C y sigue C → A → D → B → C → D. Pasa por las cinco carreteras una vez cada una y acaba en D.

Ahora sube a cinco pueblos y une todos con todos. Son 10 carreteras, y a cada pueblo llegan 4, que es par. Todos son pares, así que se puede, y además volviendo al principio. Por ejemplo: 1 → 2 → 3 → 4 → 5 → 1 → 3 → 5 → 2 → 4 → 1.

¿Más pueblos lo hacen más difícil? No. Con 3, 5, 7… pueblos (un número impar), a cada uno llegan 2, 4, 6… carreteras, todo par, y se puede. Con 4, 6, 8… pueblos llegan 3, 5, 7…, todo impar, y como hay tantos puntos impares como pueblos, no se puede. Con 2 pueblos solo hay una carretera y es trivial. El resultado depende de si el número de pueblos es par o impar, no de que sean muchos[2].

Con Königsberg pasaría lo mismo. Si se añadiera o se quitara un puente entre dos de las zonas impares, quedarían solo dos impares y el paseo sería posible.

6. Para comprobarlo tú mismo: dibuja grafos y cuenta cuántas líneas llegan a cada punto

Dibuja en un papel unos cuantos puntos, únelos con líneas y escribe al lado de cada punto cuántas líneas llegan. Si el dibujo es de una sola pieza y los puntos impares son 0 o 2, intenta recorrerlo con el dedo; si no, prueba y comprueba que siempre sobra una línea.

Puedes probar con dibujos de verdad: una estrella, un cuadrado con sus diagonales, el mapa de tu barrio con las calles como líneas. Y si quieres un reto más, haz una tabla con 3, 4, 5, 6, 7 y 8 pueblos unidos entre sí y apunta cuántas líneas llegan a cada punto (el grado), el número de puntos impares y si se puede recorrer. Antes de dibujar, intenta adivinar el resultado con la regla.

Si quieres seguir leyendo, la ficha del archivo de Euler resume el trabajo original, y el artículo de la revista SUMA explica el problema de Königsberg y el trazo sin levantar el lápiz pensado para estudiantes[1][3].

Fuentes

Historial de cambios