Prueba del Teorema de Konig para grafos bipartitos a partir del Teorema de Menger

Question

¿Podría alguien proporcionarme una buena referencia para una prueba del Teorema de Konig para grafos bipartitos a partir del Teorema de Menger?

El Teorema de Konig es el siguiente:

Para un grafo bipartito $G$, el tamaño máximo de un emparejamiento es igual al tamaño mínimo de una cubierta de vértices.

El Teorema de Menger es el siguiente:

Sea $G$ un grafo y sean $u$ y $v$ dos vértices no adyacentes. Entonces el corte mínimo de vértices para $u$ y $v$ (el mínimo número de vértices cuya eliminación desconecta $u$ y $v$) es igual al máximo número de $u,v$-caminos mutuamente disjuntos.

¡Gracias!

Answer 1

Sea $G$ un grafo bipartito con bipartición $(A,B)$. La idea es aplicar el Teorema de Menger a un nuevo grafo $G^\prime$ obtenido de $G$ añadiendo dos vértices $u$ y $v$, y uniendo $u$ a todos los vértices en $A$, y $v$ a todos los vértices en $B.

Ahora solo necesitas comprobar que un emparejamiento en $G$ corresponde a un conjunto de caminos $(u,v)$ internamente disjuntos en $G^\prime$, y una cubierta de vértices en $G$ corresponde a un $(u,v)$-corte en $G^\prime$.