El teorema de Dirac explicado con una cena entre amigos

Dirac's Theorem at a Dinner Party

El teorema de Dirac explicado con una cena entre amigos

Gabriel Dirac, hijastro del físico Paul Dirac, formuló en 1952 un teorema clave sobre ciclos Hamiltonianos. El blog ofrece una prueba accesible usando una cena: cada invitado es un vértice y cada amistad una arista. Si todos tienen al menos n/2 amigos, se pueden sentar en una mesa redonda de modo que cada uno quede entre dos amigos. La demostración emplea movimientos tipo sillas musicales y un experimento con papas para garantizar que siempre haya un cruce que cierre las brechas.

Si cada invitado tiene al menos n/2 amigos, entonces para cualesquiera dos desconocidos, d(u)+d(v) ≥ n, así que cada brecha tiene un cruce.

Más de este día

2026-11-22