Proof that there exists complete matching.

Question

Given is bipartite graph $G = (V_1 \cup V_2, E)$. Prove that if $\exists m \in \mathbb{N} : \forall x \in V_1 , \forall y \in V_2 $ $\delta(x) \ge m \ge \delta(y) $ then exists complete matching.

Answer 1

By $\delta(x)$, I'll assume you mean the degree of $x$.

You want to apply Hall's Theorem of course. So take any $A\subseteq V_2$ and let $B\subseteq V_1$ denote the set of neighbours of $A$. You want to show that $|A|\leq |B|$.

The trick is to consider the number $a$ of edges incident to vertices in $A$, and the number $b$ of edges incident to vertices in $B$. First, check that $a\leq b$.

On the other hand, $a=\sum_{v\in A} \delta(v)$ and $b=\sum_{w\in B}\delta(w)$. I will leave it to you to finish up the proof from here.