# Bipartite Graphs and Perfect Matchings when |A|=|B|=n

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$.

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

@Koala...

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

aka.

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$$.