G is a bipartite graph, where for every edge e=(a,b)[a,b are in A,B] d(a)>d(b), and d(a)>0, show that there is a matching saturating A 
I think the direction is definitely HALL, i tried using induction on the size of S, where S is some subgroup of A, but i wasn't able to complete the process.
 A: One way to do this is the following:
First prove a lemma:
If $G$ is a bipartite graph with bipartition $X,Y$ and no isolated vertices in $X$,
such that $d(x)\geq d(y)$ whenever $x\in X$ and $y\in Y$ are adjacent.
Then $|X|\leq|Y|$.
Then for each subset $S$ of $A$ you find that the degree conditions still hold for the subgraph induced by $S\cup N(S)$. Now the lemma implies that $|S|\leq|N(S)|$ and you have verified Hall's condition.
You can prove the lemma by induction on the maximum degree.
Here are a few hints for the proof of the lemma.
Let $k$ be the maximum degree.
The induction base ($k=1$) is simple.
For the induction step, let $G$ be a smallest counterexample for the claim with maximum degree $k>1$.
Let $P$ be the vertices in $X$ with degree $k$ and $Q$ the vertices in $Y$ with degree $k$.
Now prove following statements:


*

*$P$ cannot be empty.

*$Q$ cannot be empty.

*All edges starting in $Q$ must go to $P$.

*There is a matching of $Q$ in the subgraph induced by $P\cup Q$.

*Removing the edges of this matching produces a smaller counterexample for the claim. This final contradiction shows that no such counterexample can exist.
Proof of item 2 (assuming we already proved that $P$ is not empty):
Suppose $Q$ is empty. Now we remove one single edge $px$ that has an endpoint $p$ in $P$. The remaining graph still fulfills the degree conditions (the degree of the vertices in $Q$ can only be lower, the degree of the vertices in $P$ are unchanged, except the degree of $p$, that is now $k-1$, and because $Q$ was empty all neighbours of $p$ have degree at most $k-1$). But $X$ and $Y$ are still the same, so $G$ was not the smallest counterexample. Contradiction.
