I have an exercise from here involving Hall's Theorem:
Let G be a bipartite graph on the parts $X$ and $Y$, and
suppose that the inequality $\deg(x)\ge \deg(y)\ge 1$ holds for all $x\in X$ and $y\in Y$. Prove that $X$ has a perfect matching into $Y$.
I'm thinking about proving that $\deg(x) \ge \deg(y)\implies |N(S)|\ge |S|$ for all subsets $S\subseteq X$ and then Hall's Theorem applies. I'm having trouble thinking about it this way.
Another possibility might be to suppose our condition $\deg(x) \ge \deg(y)$ does not have a perfect matching and find a contradiction. I know there's some $S\subseteq X$ s.t. $|N(S)|\lt |S|$ by Hall's Theorem under this assumption. If I let $D(S)$ be the sum of all the degrees of each $x\in S$, this equals the number of edges from $S$ which are all in $N(S)$. Since $|N(S)|\lt |S|$, we have fewer vertices in $N(S)$ than in $S$. So some vertex $y\in N(S)$ has $\deg(y)>\deg(x)$ because we have $D(S)$ edges coming from $S$ and fewer vertices to connect them to in $N(S)$. Is this a proof? Could it be clearer or am I missing something?
Best Answer
Assume that $\deg(x)\ge\deg(y)$ whenever $x\in X$ and $y\in N(x)$, and assume also that $\deg(x)\gt0$ for all $x\in X$. Then for $S\subseteq X$ we have $$|S|=\sum_{x\in S}1=\sum_{x\in S}\sum_{y\in N(x)}\frac1{\deg(x)}\le\sum_{x\in S}\sum_{y\in N(x)}\frac1{\deg(y)}$$$$=\sum_{y\in N(S)}\sum_{x\in N(y)\cap X}\frac1{\deg(y)}\le\sum_{y\in N(S)}\sum_{x\in N(y)}\frac1{\deg(y)}=\sum_{y\in N(S)}1=|N(S)|.$$ That is, Hall's condition is satisfied, so there is a matching which covers every vertex in $X$.