# Condition for perfect matching in bipartite graphs

Let $G=(V,E)$ be a bipartite graph with the bipartition $V = V_1 \cup V_2$, where $|V_1|=|V_2|=n.$

We say that $G$ satisfies the $(p,q)$-condition if \begin{aligned} &\text{(1) } \forall I \subseteq V_1 \text{ with } |I| \leq p, |I| \leq |N(I)|; \\ &\text{(2) } \forall J \subseteq V_2 \text{ with } |J| \leq q, |J| \leq |N(J)|. \end{aligned} Note that the $(n,0)$-condition is Hall's condition.

Prove that if $G$ satisfies the $(p,q)$-condition with $n \leq p+q$, then $G$ has a perfect matching.

I know how to prove the original Hall's theorem by using induction, however, in this case it seems that it doesn't work.

## 1 Answer

Let $i$ be any nonegative integer. Then as $G$ satisfies the $(p,q)$-condition, any subset $T \subset V_2$ of $q-i$ vertices must satisfy $|N(T)| \geq q-i$. Thus $N(T)$ intersects every subset $S$ of $V_1$ of size at least $n-(q-i)+1$. This implies that every subset $S$ of $V_1$ of size $n-(q-i)+1$ satisfies $N(S) \cap T$ is nonempty for every subset $T \subset V_2$ with $q-i$ vertices, which implies that $|N(S)|$ must be at least $n+1-(q-i) \ge |S|$. So for every set $S \subset V_1$ with at least $n+1-(q-i)$ elements, $|N(S)|$ is at least $|S|$.

As $n+1-(q-i)$ is no larger than $p+1$ [because $q+p$ is at least $n$], for every set $S \subset V_1$ with at least $p+1$ elements, $|N(S)|$ is at least $|S|$. Likewise, for every set $T \subset V_2$ with at least $q+1$ elements, $|N(T)|$ is at least $|T|$ too. So this and that $G$ satisfies the $(p,q)$ condition together imply that the graph must satisfy the full Hall's Condition.

• LAst sentence of first paragraph should read: "So for each $i$ satisfying $q-1 \ge i \ge 0$ every set $S$ with $n+1 -(q-i)$ elements satisfies $|N(S)| \ge |S|$. And first sentence of second paragraph should read "And (setting $i=0$) as $n+1 - q$ is no larger than $p+1$...." – Mike Jul 17 '18 at 1:42