I was studying with the recitations provided in the course 6.042 "Mathematics for Computer Science" of MIT OCW and while studying the proof of Hall's marriage problem, I understood the first proof where the bottleneck condition comes in.
However, since it is not efficient as you would need to check a billion subsets for a set of size 30, he talks of easy matching condition where he provides this theorem.
Theorem - "Let G be a bipartite graph with vertex partition L,R where $L \leq R$. If G is degree-constrained, then there is a matching that covers L."
and he has provided this def for the term "degree constrained".
Theorem ( for reference ) - "A bipartite graph G with vertex partition L, R where $L \leq R$ is degree-constrained if $deg(l) \geq deg(r)$ for every $l \in L$ and $r \in R$. "
He has proved the matching theorem by contradiction. But I am having problem understanding the theorem!! Can you provide a better or simple explanation for the same.
EDIT 1: Following is the proof provided in their "readings" section :
The proof is by contradiction. Suppose that G is degree constrained but that there is no matching that covers L. This means that there must be a bottleneck $S \subseteq L$. Let x be a value such that $deg(l) \geq x \geq deg(r)$ for every $l \in L$ and $r \in R$.
Since every edge incident to a node in S is incident to a node in N(S), we know that $$|N(S)|x \geq |S|x$$ and thus that $$|N(s)| \geq |S|$$
This means that S is not a bottleneck, which is a contradiction. Hence G has a matching that covers L.
I am having problem that how did they obtain $$|N(S)|x \geq |S|x$$ in the first place!! Please also provide a brief intuition, if possible, for the same.
Let's let $A$ be the number of edges incident to vertices in $S$ and let $B$ be the number of edges incident to vertices in $N(S)$.
We must have $A\leq B$ since every edge incident to a vertex in $S$ is definitely incident to a vertex in $N(S)$ by definition of $N(S)$. (It may be that $A\neq B$ since an edge incident to a vertex in $N(S)$ may not be incident to a vertex in $S$, but that's ok, $A\leq B$ is all we need).
On the other hand, the choice of $x$ means that $$A=\sum_{l\in S}\deg(l)\geq \sum_{l\in S}x=|S|x$$ and $$B=\sum_{r\in N(S)}\deg(r)\leq \sum_{r\in N(S)}x=|N(S)|x.$$
So we get $|S|x\leq A\leq B\leq |N(S)|x$.