Question

Hall’s theorem. Returning to the matchmaking scenario of Section 7.3, suppose we have a bipartite graph with boys on the left and an equal number of girls on the right. Hall’s theorem says that there is a perfect matching if and only if the following condition holds: any subset $\mathit{s}$of boys is connected to at least $\mathbf{\left|}\mathit{s}\mathbf{\right|}$girls.

Prove this theorem. (Hint: The max-flow min-cut theorem should be helpful.)

Short answer

The Hall’s theorem is proved by the contradiction of perfect matching.

Step-by-step solution

Explain Bipartite matching

Bipartite matching checks for the perfect matches between the edges between the set of boys and girls. Perfect matching occurs if and only if the number of flows size equals the number of couples.

Prove the Hall’s Theorem.

Consider the bipartite graph G with a set A of boys and a set B of girls in equal number. The subset of boys and girls is denoted by $s$. Consider that the perfect matching exits, then $\mathrm{\forall }X\subseteq A$, there exists a subset that is connected to at least $\left|s\right|$girls. For a contradiction, assume that there is no perfect matching.

Consider the modified graph $G^{\mathrm{\prime }}$, equal to G. In $G^{\mathrm{\prime }}$add a source vertex $s$connected to every vertex in A , and a sink vertex t connected to every vertex in B. Let $f^{\star }$be the maximum flow in $G^{\mathrm{\prime }}$. Since there is no perfect matching in $G$, $f^{\star }\le \left|A\right|-1$. By the max-flow min-cut theorem, the minimum cut $X^{\ast }$must have fewer than $\left|A\right|-1$cut edges.

Every one of the vertices in $A\mathrm{\setminus }{X}^{\ast }$contributes at least one cut edge to in$x^{\ast }$, $N\left(A^{\ast }\right)|<|A^{\ast }\mid$violate the Hall’s condition.

Therefore, by the proof by contradiction, the theorem is proved.