Hall's marriage problem, graph theoretic version

Question

Let $G = ( V,E)$ be a bipartite graph, where $V = V_1 \cup V_2$ , $|V_1| \leq |V_2|$ .

For every $A \subseteq V_1$ let $\phi(A) $ be the set of vertices in $V_2$ adjacent to vertices in $A$. By hypotheses we have $$|A| \leq |\phi(A)| \ \ \forall \ A \subseteq V_1 $$

We create $2$ new vertices, $v$ and $w$ , then we link $v$ with an edge to every vertex in $V_1$, and $w$ to every vertex in $V_2$ , obtaining a new graph $G'$. Let $S$ be a minimal set of vertices in $G'$ such that by removing $S$ we disconnect $v$ from $w$.

I want to prove that $|S| = |V_1| $. I am stuck in proving that $|S| \leq |V_1| $, how to prove this part ?

Answer 1

Hint: Let $A\subseteq V_1$ be the vertices not in $S$. Show that $\phi(A)\subseteq S\cap V_2$. Conclude that $|V_1|\le |S|.$

Answer 2

You can look up the proof of Hall's marriage theorem (graph theoretic version) as theorem 2.1.2 (page 38) in Diestel's "Graph Theory" 4th edition, ISBN-10: 3642142788. This is great book in general about graph theory: I highly recommend it.