El origen de la teoría de grafos se remonta al siglo XVIII, con el famoso problema de los Puentes de Königsberg, considerado uno de los primeros problemas en la historia de la topología y la teoría de grafos. Königsberg, una ciudad ubicada en Prusia (actualmente Kaliningrado, Rusia), estaba atravesada por el río Pregolia y contenía dos grandes islas que estaban conectadas entre sí y con las orillas del río mediante siete puentes.

El problema planteado era simple pero intrigante: ¿Era posible pasear por la ciudad cruzando cada uno de los siete puentes una sola vez y volver al punto de partida?

En la imagen de abajo se muestra un esquema del mapa de la ciudad de Königsberg, con el río Pregolia dividiendo el plano en cuatro regiones distintas (A, B, C y D), que están unidas a través de los siete puentes.

Este desafío capturó la imaginación de la gente, ya que, a pesar de los intentos, nadie lograba encontrar un camino que satisficiera estas condiciones.

La solución a este problema fue proporcionada por Leonhard Euler, un matemático suizo, en 1736. Euler se dio cuenta de que la ubicación de las tierras y la longitud de los puentes eran irrelevantes para el problema; lo que importaba era simplemente si los puentes podían recorrerse en un camino continuo sin repetir ninguno. Euler abstrajo el problema a una forma que ahora reconocemos como un grafo, donde las masas de tierra (las islas y las orillas del río) se representaban como nodos (o vértices) y los puentes como aristas que conectaban estos nodos.

En la imagen inferior se muestra el grafo correspondiente al esquema del mapa de la ciudad de Königsberg.

Euler demostró matemáticamente que para que exista un camino que pase una sola vez por cada puente (un camino euleriano), no debe haber más de dos nodos con un número impar de aristas. En el caso de los puentes de Königsberg, cada una de las cuatro masas de tierra estaba conectada por un número impar de puentes (tres o cinco), por lo que concluyó que tal camino era imposible.

Este análisis no solo resolvió el problema, sino que también sentó las bases para la teoría de grafos, un campo matemático que estudia las propiedades y aplicaciones de los grafos en diversas áreas como la informática, la ingeniería, la biología y las ciencias sociales. La contribución de Euler al problema de los Puentes de Königsberg es tan fundamental que a menudo se le considera el padre de la teoría de grafos.