El grafo de Königsberg

Para responder la pregunta, Euler tuvo una idea bastante sencilla pero genial: elaboró un modelo matemático que hoy en día se llama grafo. En él, representó cada región con un punto (vértice) y cada puente, con una línea (arista).

Euler demostró que no existía un camino que contuviera a todas las aristas del grafo sin que ninguna se repitiera. ¡Inténtalo! Trata de dibujar el grafo de los puentes de Königsberg sin levantar el lápiz del papel y sin volver a pasar por ninguna línea.

Euler definió el grado de un vértice del grafo como el "número de aristas que inciden en él". Probó que, si el grafo tiene más de dos vértices de grado impar, no se puede trazar un camino que contenga a todas sus aristas sin que ninguna se repita. Pero, si tiene sólo dos vértices o ningún vértice con grado impar, entonces sí se puede trazar el camino.

Por ejemplo, el grado del vértice 4 del grafo de Königsberg es 5, y el grado de los otros tres es 3. Es decir, hay más de dos vértices de grado impar, por lo que no es posible caminar por toda la ciudad cruzando cada uno de los siete puentes, exactamente, una sola vez.

Hoy en día, la teoría de Euler se utiliza para jugar a trazar figuras sin levantar el lápiz del papel y sin pasar dos veces por una misma línea.

¡A jugar!

¿Cuál de las figuras se puede dibujar sin levantar el lápiz del papel y sin pasar dos veces por la misma línea? (Se muestran cuatro figuras: un triángulo dividido en cuatro triángulos, un cuadrado con diagonales, una casita con diagonales y techo, y un rombo alargado con cruces).