El Teorema de Hall

Teoría

El Teorema del Matrimonio de Hall es un resultado fundamental en la teoría de gráficas combinatoria que da una condición necesaria y suficiente para que exista un emparejamiento (matching) que cubra un conjunto específico de vértices en una gráfica bipartita. En el contexto del clásico "problema del matrimonio", si tienes un conjunto de personas $X$ y un conjunto de parejas potenciales $Y$, el teorema determina si es posible emparejar a cada persona en $X$ con una pareja distinta en $Y$ de tal manera que todos estén felices con su asignación.

Este teorema es crucial en las matemáticas olímpicas porque traduce una propiedad estructural global (la existencia de un emparejamiento perfecto o un Sistema de Representantes Distintos) en una condición local que puedes verificar usando subconjuntos. Se usa frecuentemente para resolver problemas de existencia en combinatoria, como llenar cuadrados latinos, resolver conflictos de horarios o demostrar otros teoremas importantes como el Teorema de Dilworth sobre conjuntos parcialmente ordenados.

La intuición clave detrás del Teorema de Hall es el concepto de "cuello de botella". Para que exista un emparejamiento, es obviamente necesario que para cualquier grupo de $k$ personas, el conjunto total de parejas que están colectivamente dispuestas a aceptar debe contener al menos a $k$ personas. Si a un grupo de 5 personas colectivamente solo les gustan 4 parejas distintas, es imposible lograr un emparejamiento por el Principio de las Casillas. El Teorema