I have to solve this exercise:
Let G = (S, T; E) a biregular graph. Prove that in this graph there exist a matching that either saturates all the vertices in S or saturates all the vertices in T.
From what I know, I have to use Hall's Theorem, but I have no clue how to do so.
Any hint is appreciated. Thank you.
Suppose WLOG that $|S| \leq |T|$. Let the degree of each vertex in $S$ be $d_S$ and the degree of each vertex in $T$ be $d_T$.
Take any subset $W \subseteq S$. Let $N(W)$ denote the set of neighbors of verties in $W$. Let $G'$ be the induced bipartite subgraph with vertex sets $W$ and $N(W)$. Then $|E(G')|$, the number of edges in $G'$, satisfies $$ |E(G')| = d_S \cdot |W| .$$ Since we have drawn $|E(G')|$ edges which are incident to $N(W)$ vertices, there must be a vertex in $N(W)$ with degree $\geq \frac{|E(G')|}{|N(W)|}$. So $$ d_T \geq \frac{d_S \cdot |W|}{|N(W)|} .$$
But now notice that since $|S| \cdot d_T = |E(G)| = |T| \cdot d_S$, we have $$ d_S \geq d_T. $$
Combining these ineqalities, we get $$ d_S \geq \frac{d_S \cdot |W|}{|N(W)| } ,$$
which simplifies to $|W| \leq |N(W)|$. By Hall's theorem, we are done.