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.

  • 1
    $\begingroup$ How far have you gotten? Have you found an example as demanded in the last sentence? $\endgroup$ – bof Dec 5 '14 at 17:19
  • $\begingroup$ I'm struggling with Hall's theorem to prove the first part.... $\endgroup$ – Erfan Dec 5 '14 at 17:30
  • $\begingroup$ 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? $\endgroup$ – bof Dec 5 '14 at 17:48
  • $\begingroup$ 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.... $\endgroup$ – Erfan Dec 5 '14 at 18:55

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


  • $(\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$

  • $\begingroup$ It sure did.Problem solved ! $\endgroup$ – Erfan Dec 6 '14 at 20:39
  • $\begingroup$ Also I guess $ N(S \cap X) $ and $ N(S \cap Y) $ are disjoint because a matching has non-adjacent links. $\endgroup$ – Erfan Dec 6 '14 at 20:48
  • $\begingroup$ @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)$? $\endgroup$ – dtldarek Dec 6 '14 at 21:13
  • $\begingroup$ $ 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 ?! $\endgroup$ – Erfan Dec 11 '14 at 15:54
  • $\begingroup$ @elkoldo Correct. $\endgroup$ – 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.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.