Matching in a bipartite graph that saturates all vertices

Question

Let $G=(S,T;E)$ be a bipartite graph without isolated vertices.

For every edge $e\in E$, e $=$ $st$ $($ s $\in S$, $ t\in T$) happens the inequality $dG(s)$ $>=$ $dG(t)$.

Prove that in $G$ exists a matching which saturates all the vertices of S.

My thoughts:

I found that there exists $Theorem$ $Hall(1935)$ which says:

Let $G$ $=$ $(S,T;E)$ be a bipartite graph. There exists a matching in $G$ which satures all the vertices in $S$ if only and only

$|NG(A)|$ $>=$ $|A$|, $∀A ⊆ S$. (NG represents the neighbors i suppose)

But I don't know how to apply this theorem to my problem, or if anyone has other ideas?

Answer 1

The saturation part actually just says there is a matching $E_M$ with $$\forall_{s \in S} \exists_{t \in T} [e(s,t) \in E_M]$$

Then use Hall's marriage theorem in its Graph theoretic formulation.

It suggests to use contradiction by finding a matching $E_M$ that has $s \in S$ and no $t_M \in T$ in the matching. By the properties you should try to prove that a better matching $E'_M$ exists, that does include $s$.

The alternating paths strategy might work, or you may need to modify it a bit using your inequality.