# Perfect matching in bipartite graphs

Prove that a bipartite graph $G = \left(V,E\right)$ has a perfect matching $\iff$ $\vert N(S)\vert\geq \vert S \vert$ for all $S \subseteq V$. (For any set $S$ of vertices in $G$ we define the neighbor set $N(S)$ of $S$ in $G$ to be the set of all vertices adjacent to vertices in $S$.) Also give an example to show that the above statement is invalid if the condition that the graph be bipartite is dropped.

• How far have you gotten? Have you found an example as demanded in the last sentence? – bof Dec 5 '14 at 17:19
• I'm struggling with Hall's theorem to prove the first part.... – Erfan Dec 5 '14 at 17:30
• Why doesn't it follow immediately from Hall's theorem? Isn't Hall's condition just $|N(S)|\ge|S|$? What goes wrong, where do you get stuck? – bof Dec 5 '14 at 17:48
• Well problem is that, in Hall's theorem we have a bipartition (X,Y) and S is necessarily a subset of X, but here S is an arbitrary subset of V, meaning it can have elements in both X and Y.... – Erfan Dec 5 '14 at 18:55

Let $X\uplus Y = V$ be the bipartition of $G$.

Hint:

• $(\Leftarrow)$ Any $S\subseteq V$ in particular means any $S\subseteq X$ and any $S\subseteq Y$.
• $(\Rightarrow)$ Perfect matching is both $X$-saturating and $Y$-saturating, so the Hall's condition works for both sides. Apply Hall's theorem two times for $S\cap X$ and $S \cap Y$ and you are done (why $N(S\cap X)$ and $N(S\cap Y)$ are disjoint?).

I hope it helps $\ddot\smile$

• It sure did.Problem solved ! – Erfan Dec 6 '14 at 20:39
• Also I guess $N(S \cap X)$ and $N(S \cap Y)$ are disjoint because a matching has non-adjacent links. – Erfan Dec 6 '14 at 20:48
• @elkoldo For the proof to work, you need that $|N(S \cap X)| + |N(S \cap Y)| = |N(S)|$, but that only works if these sets are disjoint. Hint: to which side of the bipartition belong vertices of $N(S \cap X)$ and $N(S \cap Y)$? – dtldarek Dec 6 '14 at 21:13
• $N(S \cap X)$ and $N(S \cap Y)$ belong respectively to $Y$ and $X$ , and since $X$ and $Y$ are different sides of the bipartition, $N(S \cap X)$ and $N(S \cap Y)$ are disjoint. Right ?! – Erfan Dec 11 '14 at 15:54
• @elkoldo Correct. – dtldarek Dec 11 '14 at 16:09

Hint: Apply Hall's Theorem to the (bipartite) graph obtained by taking two disjoint copies of your given bipartite graph.