[Math] Perfect matching in bipartite graphs

bipartite-graphsgraph theorymatching-theory

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.

Best Answer

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$

Related Question