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