Los Siete Puentes de Königsberg son un problema matemático históricamente famoso. Leonhard Euler lo resolvió en 1735 (publicado en 1736 bajo el título latinizado Solutio problematis ad geometriam situs pertinentis). Su solución estableció las bases de la moderna teoría de grafos y contribuyó al desarrollo temprano de la topología (entonces llamada «geometría del lugar» o «analysis situs»).

La ciudad de Königsberg, en Prusia (actualmente Kaliningrado, Rusia), estaba situada a ambos lados del río Pregel. Incluía dos grandes islas que estaban conectadas entre sí y con el continente por siete puentes. El problema planteado popularmente consistía en encontrar un paseo que atravesara la ciudad cruzando cada puente una y sólo una vez.

Las reglas eran sencillas: no existía acceso a las islas más que por esos puentes, cada puente debía recorrerse por completo al cruzarlo y no era necesario que el paseo comenzara y terminara en el mismo punto. Euler demostró que tal paseo no existe.

La clave de la demostración de Euler fue abstraer el mapa real en una estructura más simple: representar cada masa de tierra (las dos orillas y las dos islas) por un punto, y cada puente por una línea que une los puntos correspondientes. Esta abstracción es precisamente la idea central de la teoría de grafos: vértices (puntos) y aristas (líneas).

Con esa representación, Euler observó lo siguiente, que puede entenderse de forma intuitiva:

  • Cada vez que uno pasa por una masa de tierra sin empezar ni terminar ahí, entra por un puente y sale por otro, lo que contribuye con dos a la cuenta total de puentes que tocan esa masa (es decir, al grado del vértice).
  • Por tanto, excepto posiblemente en los puntos de inicio y final del paseo, el número de puentes que llegan a cada masa de tierra debe ser par.
  • De ahí se desprende la condición general para que exista un paseo que cruce cada arista exactamente una vez (un paseo euleriano): en un grafo conectado debe haber 0 o 2 vértices de grado impar. Si hay 0, existe un ciclo euleriano (comienza y termina en el mismo vértice); si hay 2, existe un camino euleriano que comienza en uno de los vértices impares y termina en el otro.

Al aplicar este criterio al grafo de Königsberg, Euler comprobó que había más de dos vértices con número impar de puentes colindantes (en la representación clásica los grados son impares en las cuatro masas de tierra), por lo que el paseo requerido era imposible.

Consecuencias e importancia:

  • La solución de Euler es el origen reconocido de la teoría de grafos, que abstrae problemas de rutas, redes y conexiones y tiene hoy aplicaciones en informática, logística, biología (ensamblaje de genomas), telecomunicaciones y muchas otras áreas.
  • Introdujo la idea de estudiar propiedades globales de las figuras sin depender de medidas: una de las raíces de la topología.
  • Generó problemas y algoritmos relacionados, como el problema del cartero chino (minimizar recorridos que cubran aristas) y procedimientos para construir caminos eulerianos cuando existen (por ejemplo, el algoritmo de Hierholzer para encontrar ciclos eulerianos).

En suma, el rompecabezas de los Siete Puentes de Königsberg es mucho más que una curiosidad histórica: es un ejemplo didáctico que muestra cómo la abstracción matemática puede convertir un sencillo problema práctico en la semilla de disciplinas enteras.