Teorema de Hall
(Tenga en cuenta que esto no es único: (2, 1, 3 funciona igualmente bien, por ejemplo.)
Ejemplo 2: Considere S = {A1, A2, A3, A4} con No existe ninguna transversal válida.
Considere si es posible hacer pareja (en el matrimonio) a los hombres y mujeres para que cada persona sea feliz.
Si dejamos que Ai sea el conjunto de hombres que la mujer i-th sería feliz de casarse, entonces el teorema del matrimonio establece que cada mujer puede casarse felizmente con un hombre si y sólo si la colección de conjuntos {Ai} cumple con la condición de matrimonio.
, ser al menos tan grande como el número de mujeres en ese subconjunto,
el conjunto de todos los vértices en Y adyacentes a algún elemento de W. El teorema del matrimonio en esta formulación establece que hay un emparejamiento que abarca completamente X si y solo si para cada subconjunto W de X: En otras palabras cada subconjunto W de X tiene suficientes vértices adyacentes en Y.
Una generalización para grafos en general (no necesariamente bipartitos) es proporcionada por el Teorema de Tutte.
Sea M un emparejamiento máximo, y u un vértice no saturado por M. Considere todos los caminos alternativos (es decir, caminos en G que alterna entre aristas hacia afuera y hacia adentro en M) comenzando desde u.
Sea T el conjunto de todos los puntos de Y conectados a u por estos caminos alternativos, y W el conjunto de todos los puntos en X conectados a u por estos caminos alternativos (incluyendo u).
Un camino alternativo no maximal puede terminar en un vértice en Y, para que no sea un camino aumentativo, para que pudiéramos aumentar M a un emparejamiento estrictamente mayor.
Por otra parte, NG(W) ⊆ T: deje v en Y se conecte a un vértice w in W. Si la arista (w,v) está en M, entonces v esta en T por la parte anterior de la demostración, por otra parte podemos tomar un camino alternativo que acaba en w y extenderlo con v, obteniendo un camino aumentativo y mostrando que v esta en T. Por lo tanto, |NG(W)| = |T| = |W| − 1, una contradicción.
Sea S = (A1, A2,..., An) donde los Ai son conjuntos finitos no necesariamente distintos.
De forma más abstracta, sea G un grupo, y H un subgrupo finito de G. Entonces el teorema del matrimonio puede usarse para demostrar que hay un conjunto T tal que T es una transversal tanto para el conjunto de cosets izquierdos y cosets derechos de H en G. El teorema del matrimonio se utiliza en las pruebas habituales del hecho de que un Rectángulo Latino (r × n) siempre puede extenderse a un Rectángulo latino ((r+1) × n) cuando r < n, y así, últimamente a un Cuadrado latino.
El siguiente ejemplo, de Marshall Hall, Jr., muestra que la condición matrimonial no garantiza la existencia de un transversal en una familia infinita en la que se permiten conjuntos infinitos.
La condición matrimonial es válida para esta familia infinita, pero no puede construirse transversal.
