# A condition ensuring that a bipartite graph have a perfect matching

There is a bipartite graph $G=(A,B,E)$ such that for every edge $(a,b)$ (where $a$ comes from $A$ and $b$ from $B$), $\deg(a) \geq \deg(b)$, and additionally $\deg(a) \geq 1$ for all $a \in A$. From this, how can I prove there is matching which covers all of $A$?

• Have you tried using Hall's criterion? Feb 25 '16 at 16:01
• Yes, withous success so far. Feb 25 '16 at 16:12

In more detail, suppose that Hall's criterion didn't hold. Choose a set $X$ of minimal size satisfying $|N(X)| < |X|$. Show that $X$ is not empty, and let $Y = X \setminus \{x\}$ for some arbitrary $x \in X$. Show that $Y$ has a perfect matching with $N(Y)$, and prove that $N(N(Y))=Y$ by counting the edges connecting $Y$ and $N(Y)$ in two ways. Show that $\emptyset \neq N(x) \subseteq N(Y)$, and reach a contradiction.