Planteamiento del problema: Los puentes de Königsberg

Un problema clásico

Königsberg era el nombre de una ciudad atravesada por el río Preger. En el siglo XVIII era una ciudad alemana, pero ahora pertenece a Rusia y su nombre es Kaliningrado. Dentro de la ciudad hay dos islas fluviales que están conectadas a los lechos del río por puentes. En el siglo XVIII eran siete y estaban dispuestos como se muestra a continuación.

Se convirtió en tradición que los habitantes de Königsberg pasaran sus domingos por la tarde paseando por la ciudad. Se cree que intentaban cruzar cada uno de los siete puentes que unen el norte y el sur del río a las dos islas, pero sólo una vez y sin volver sobre sus pasos. ¿Es posible hacerlo?

Esto es equivalente a preguntarse si es posible caminar por la ciudad de tal manera que se cruce una sola vez cada puente.