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.


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.

  • $\begingroup$ 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$...." $\endgroup$ – Mike Jul 17 '18 at 1:42

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.