Un problema bien conocido en la teoría de grafos es el de los Siete Puentes de Königsberg. En Leonhard Euler, día de Königsberg tenía siete puentes que conectan dos islas en el Río Pregel con el continente, dispuestas como este:
Euler demostró que era imposible encontrar un paseo por la ciudad que iba a cruzar cada puente una sola vez y sólo una vez. Y, más en general, que un camino Euleriano no existe para un gráfico con más de dos nodos de grado impar.
La 2 Guerra mundial cambió la topología de la ciudad por la destrucción de dos de los puentes. (También trajo otros cambios, tales como la transferencia del territorio de Alemania a Rusia, pero esto no es topológicamente pertinentes.) Esto conducirá a la similar pero solucionable problema de los Cinco Puentes de Kaliningrado.
Dudo que los Británicos y las fuerzas aéreas Soviéticas creación de una Euler pie una prioridad cuando se estaban llevando a cabo sus ataques. Pero si lo hubieran hecho, habría que criticar a su ineficiencia, porque se podría haber logrado el mismo objetivo por el bombardeo de sólo un puente:
La generalización del problema:
¿Cuál es el mínimo número de aristas que deben ser eliminados a partir de una gráfica, de modo que los bordes restantes forman un camino Euleriano?
Mi primera conjetura fue que sería la mitad el número de "extra" impar grado de los nodos. Sin embargo, una simple forma de X gráfico proporciona un contraejemplo: Hay 4 nodos impares (y 1), pero dos bordes necesitan ser eliminados, no sólo uno.
