Question: Consider a bipartite graph G with vertex classes A and B, where $|A|=|B|=n$. Show that if $|N(S)|>|S|$ for all $S \subset A$, then for any edge e of G, G contains a perfect matching which contains e.

Answer: So far I have shown that G contains a matching which contains e using Hall's Theorem however I am unsure about how to show that this matching is perfect. I have the following theorem:

Let G be a bipartite graph with vertex classes A and B and $|A|=|B|=n$. If $\delta (G) \geq n/2$, then G has a perfect matching.

But I don't know how to show the $\delta (G) \geq n/2$ part in this case?


I think Hall's theorem is sufficient. Note that in your problem you have $|N(S)| > |S|$ with strict inequality (presumably for nonempty strict subsets $S$ of $A$), while Hall's theorem only requires the non-strict inequality.

Let $G'$ be the result of removing the edge $e$ and its two vertices (call them $a \in A$ and $b \in B$) from $G$. Let $A'$ and $B'$ be the partition of the vertices of $G'$.

It then suffices to show that the smaller bipartite graph $G'$ satisfies its own condition for Hall's theorem.

Let $S'$ be any subset of $A'$. Since it is a subset of $A$ as well, it satisfies $|S'| < |N_G(S')|$, so $$|S'| \le |N_G(S')| - 1 \le |N_{G'}(S')|$$ since the sets $N_{G'}(S')$ and $N_G(S')$ can differ by at most one vertex, namely $b$.

  • $\begingroup$ So it if fine for me to state that since Hall's theorem holds the matching is perfect? $\endgroup$
    – Koala
    Oct 29 '17 at 21:41
  • $\begingroup$ It isn't anything to do with |A|=|B|=n part? $\endgroup$
    – Koala
    Oct 29 '17 at 21:42
  • $\begingroup$ @Koala Hall's theorem ensures a matching that covers $A$, so if $|A|=|B|$ this is a perfect matching. $\endgroup$
    – angryavian
    Oct 29 '17 at 21:43
  • $\begingroup$ Oh I see :') Thanks so much! $\endgroup$
    – Koala
    Oct 29 '17 at 21:45


Can you mention cite the theorem which you have mentioned in the question


Let $G$ be a bipartite graph with vertex classes $A$ and $B$ and $|A|=|B|=n$. If $\delta(G)\geq n/2$, then $G$ has a perfect matching.

Where did u find this theorem?

I know a similar theorem called Dirac's theorem, but that works for general graphs which have minimum degree of each vertex to be at least $n/2$.


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.