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.

  • $\begingroup$ It would help if you provided the proof that you don't understand (or say exactly where it can be found) and maybe explain which parts are confusing. Otherwise, someone may just provide that same proof again and you're wasting their time. $\endgroup$ – Casteels Nov 12 '14 at 11:09
  • $\begingroup$ @Casteels I have updated it with the proof I am facing difficulty with!! $\endgroup$ – thisisashwani Nov 12 '14 at 12:02

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


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.