En un grafo bipartito con 2 emparejamientos saturando un subconjunto de ambos lados, encuentra un emparejamiento que sature ambos subconjuntos.

Question

Se nos da un grafo bipartito $G$ con partes $X,Y$; y también dos emparejamientos $M,M'$ tal que $M$ satura $S\subset X$, y $M'$ satura $T\subset Y$. Necesito demostrar la existencia de un emparejamiento que sature tanto $S,T$.

Intenté comenzar desde el emparejamiento $M$ eliminando cualquier arista en $M$ que no sature un vértice en $S$, y luego incluir cualquier arista $e_i\in M'$ que sature algún $v_i\in T$ que aún no esté saturado. Pero si agrego una arista así, podría estar unida a un vértice $v_i\in S$ que ya está saturado. Entonces tendría que eliminar la arista actual que lo satura, y así sucesivamente. No sé cómo explicar rigurosamente por qué este método funcionará (o tal vez no lo hará y lo estoy abordando mal).

¿Alguien sabe cómo hacer esto de manera más rigurosa?

Answer 1

Sea $\overrightarrow{M}$ los bordes de $M$ orientados desde $X$ a $Y$ y sea $\overrightarrow{M'}$ el conjunto de bordes en $M'$ orientados desde $Y$ a $X$. Cualquier ciclo en $\overrightarrow{M} \cup \overrightarrow{M'}$ puede ser "cancelado" eliminando los bordes contribuidos por, digamos, $\overrightarrow{M}$, dejando un bosque orientado $F$ en el cual cada vértice en $S$ y $T$ tienen grado de salida $1$. El grado de salida de los vértices en $S$ y $T$ implica que los caminos máximos no terminan ni en $S$ ni en $T$. Por lo tanto, también podemos "cancelar" caminos máximos (de longitud al menos 2) manteniendo solo los bordes en el camino que provienen de $\overrightarrow{M}$ si el camino comienza en $S$, o solo los bordes en $\overrightarrow{M'}$ si el camino comienza en $T$.

Después de cancelar todos los caminos máximos de longitud al menos dos, solo quedan arcos independientes, y cada vértice en $S \cup T$ está incidente a un arco; los bordes subyacentes forman el emparejamiento deseado.