Veo que esta pregunta se hizo hace bastante tiempo, pero es un resultado excelente que cualquier estudiante de teoría de grafos debería ver no obstante. Muchos estudiantes de teoría de grafos no se dan cuenta de que el teorema de Tutte es una generalización del teorema de Hall. Tuve la suerte de tener un profesor que lo demostró explícitamente en clase, y me complace recrear esa demostración aquí para que otros estudiantes de teoría de grafos puedan ver la conexión entre estos teoremas. La demostración que aprendí es a través de una serie de lemas:
Teorema. El teorema de Hall se deriva del teorema de Tutte.
Prueba. Dejemos que $G$ sea un grafo bipartito de orden $n$ con bipartición $(X, Y)$ . Consideremos el gráfico auxiliar $H$ obtenido de $G$ añadiendo un vértice más al conjunto de la partita $Y$ si $n$ es impar, entonces añadiendo todas las aristas entre vértices de $Y$ para hacer $Y$ una camarilla.
Lema 1. $G$ tiene una coincidencia de tamaño $\vert X \vert$ si y sólo si $H$ tiene una correspondencia perfecta.
Pf. $(\Rightarrow)$ Supongamos primero que $G$ tiene una coincidencia de tamaño $\vert X \vert$ . Desde $G$ es bipartita, cada arista del emparejamiento tiene un punto final en $X$ y el otro en $Y$ . Desde $H[Y]$ es una camarilla, podemos emparejar vértices de $Y$ arbitrariamente para completar una coincidencia perfecta en $H$ (nota que $H$ tiene un orden uniforme por construcción, por lo que el emparejamiento que formamos es realmente perfecto).
$(\Leftarrow)$ Supongamos ahora que $H$ tiene una correspondencia perfecta. Desde $H[X]$ es independiente (ya que $G$ es bipartita), un emparejamiento perfecto en $H$ debe utilizar $\vert X \vert$ bordes para saturar $X$ . Estas aristas forman un emparejamiento de tamaño $\vert X \vert$ en $G$ , demostrando la pretensión deseada. $\square$
Lema 2. Si $G$ satisface la condición de Hall, $H$ satisface la condición de Tutte.
Pf. Supongamos que $G$ satisface la condición de Hall, es decir, para cualquier $S \subseteq X, \vert N(S) \vert \geq \vert S \vert$ . Sea $T \subseteq V(H)$ para verificar que $H$ satisface la condición de Tutte, debemos demostrar que $o(H - T) \leq \vert T \vert$ . Desde $H[Y \cap T]$ es una camarilla, los componentes Impares de $H - T$ son los vértices de $X$ todos sus vecinos se encuentran en $T$ , posiblemente junto con $Y - T$ (sólo si $T$ se elige de manera que $\vert Y - T \vert$ es impar). Set $$S = \{x \in X : N(x) \subseteq Y \cap T\}$$ (es decir, los vértices de $X$ que se aíslan al suprimirse el $T$ de $H$ ). Dado que $G$ satisface la condición de Hall, tenemos que $$\vert S \vert \leq \vert T \cap Y \vert \leq \vert T \vert,$$ y por lo tanto $$o(H - T) \leq \vert T \vert + 1.$$ Sin embargo, como $H$ es de orden par, $o(H - T)$ y $\vert T \vert$ deben tener la misma paridad, y obtenemos $o(H - T) \leq \vert T \vert$ Por lo tanto $H$ satisface la condición de Tutte, como se iba a demostrar. $\square$
Con los lemas anteriores, la prueba real (que el teorema de Hall se deriva del teorema de Tutte) es casi inmediata. Como siempre, la necesidad de la condición de Hall es obvia (tener un emparejamiento que sature $X$ cualquier subconjunto de $X$ debe tener al menos tantos vecinos como elementos para ser completamente compatible). Para ver por qué la suficiencia del teorema de Hall se deduce de Tutte, dejemos que $H$ sea el gráfico auxiliar considerado a lo largo de esta prueba. Dado que $G$ satisface la condición de Hall (por supuesto), $H$ satisface la condición de Tutte (lema 2). Dado que $H$ satisface la condición de Tutte, tiene una correspondencia perfecta (por el teorema de Tutte). Por último, dado que $H$ tiene una correspondencia perfecta, podemos concluir que $G$ tiene una coincidencia de tamaño $\vert X \vert$ como se desea (lema 1). Esto completa la prueba. $\square$
Observaciones. Me gustaría reiterar que esta prueba no es mía, sino una que mi profesor de teoría de grafos presentó en una conferencia hace algunos años (quién sabe dónde la vio por primera vez). He desenterrado mi cuaderno y he intentado recrear lo que mostraron lo más fielmente posible. Espero que esta respuesta sacie por fin su curiosidad, y ojalá pueda ayudar a los estudiantes de teoría de grafos en el futuro a ver exactamente por qué el teorema de Tutte es una generalización del teorema de Hall. Si alguno de los argumentos escritos aquí no está claro, no dudes en pedirme una aclaración.
