En el siglo XVIII, la ciudad prusiana de Königsberg tenía siete puentes sobre su río, y la gente se preguntaba: ¿se podrá hacer un recorrido que cruce cada puente exactamente una vez? Cuando el matemático Euler respondió esa pregunta, nació una rama totalmente nueva de las matemáticas: la teoría de grafos.
Si reduces cada porción de tierra a un punto y cada puente a una línea, obtienes el diagrama de abajo. Haz clic en los puntos en orden para cruzar cada puente exactamente una vez; no puedes repetir un puente. Inténtalo todas las veces que quieras y comprueba si de verdad se puede.
Haz clic en cualquier punto para empezar y luego en los siguientes puntos en orden para intentar cruzar los siete puentes.
Elige una figura e intenta dibujarla de un solo trazo. Comprueba tú mismo qué figuras se pueden y cuáles nunca.
El número de líneas que llegan a un punto se llama su grado. Si cuentas cuántos puntos tienen grado impar (vértices impares), puedes saber de antemano si se puede dibujar de un solo trazo.
0 vértices impares → puedes empezar en cualquier punto, dibujarla de un solo trazo y terminar donde empezaste (un circuito euleriano).
2 vértices impares → solo se puede si empiezas en uno de ellos y terminas en el otro (un camino euleriano).
3 o más vértices impares → nunca se puede dibujar de un solo trazo. ¡Königsberg tenía cuatro, y justo por eso no se podía!
Cada vez que tu trazo pasa por un punto, usa una línea para entrar y otra para salir, siempre en pareja. Así que en cualquier punto que no sea ni el inicio ni el final, cada visita gasta dos líneas, lo que significa que su número total de líneas (su grado) tiene que ser par.
Solo dos tipos de punto pueden tener un número impar de líneas: el inicio (sale una línea de más) y el final (llega una línea de más). Por eso puede haber como máximo dos vértices impares. Con tres o más, no todos pueden ser inicio o final, y dibujarla de un solo trazo se vuelve imposible.