So I was trying to solve this problem
Let $H$ be a bipartite graph with bipartition $A,B$ such that $|A| = |B| = k$. Prove that the graph contains a perfect matching when every vertex has degree of at least $\frac{k}{2}$
And this is what I tried:
We know that each vertex in $A$ will connect to at least half of those in $B$, and so for the converse. This means that there will be no vertex that has no direct neighbour in either bipartition. Let $A_i$ be the set of neighbours in $B$ relative to vertex $a_i \in A$. We will also let $B_i$ follow the same definition, but each neighbour is in $A$.
Hall's Theorem says that for each subset $S \subseteq [n] = \{1,2,\dots,n\},\, \left|\bigcup_{i\in S}A_i\right| \geq |S| \implies$ there exists distinct $z_i \in A_i$ for each $1 \leq i \leq n$.
I got stuck here becasue I can't see how I can apply this theorem to the problem. I could say that each $|A_i| \geq \frac{k}{2}$ but what if there exists some $A_j = A_i$? then the cardinality of the union of both sets may not be larger than 2.
Could I have a hint to continue with this?
Best Answer
Suppose Hall's criterion is not satisfied.
Then there is $X\subseteq A$ such that $|N(X)|<|X|$, where $N(X)$ denotes the set of all the vertices which are incident with at least one vertex in $X$. Clearly, $|N(X)|\geq k/2$.
Let $Y=B\setminus N(X)$. Note that $N(Y)\subseteq A\setminus X$, and therefore $|A\setminus X|\geq k/2$. But since $|X|>|N(X)|\geq k/2$, we have $|A| = |X| + |A\setminus X| > k$, which is a contradiction.