Prove bipartite graphs have a perfect matching of $X$ into $Y$ if $\deg(x)\ge \deg(y)$ for all $x\in X$ and $y\in Y$

Question

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?

Answer 1

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$.

Answer 2

I assume vertices of $X$ have positive degrees. Let me write $\deg_A (x):=d_A(x)$, which is the degree of $x$ relative to a subgraph $A$ of $G$ if $x\in V(A)$. I am not sure if this is overkill, but:

Take any $S\subseteq X$ and suppose that $|N(S)|<|S|$.

Let $A$ be the graph induced by $S$ (meaning we include all of their edges and neighbours tied to these edges). Hence, $V(A) = S \bigcup N(S)$.

Note that $E(A)=\sum_{s\in S} d_A(s)=\sum_{v\in N(S)} d_A(v)$ by counting (or handshaking!) and bipartiteness.

We have $\sum_{v\in N(S)} d_A(v)\leq \sum_{v\in N(S)} d_G(v)\leq \sum_{v\in N(S)} d_G(w)\leq |N(S)|d_G(w)<|S|d_G(w)$, where we let $w$ be the vertex of maximum degree in $N(S)$.

On the other hand, $\sum_{s\in S} d_A(s)=\sum_{s\in S} d_G(s)\geq \sum_{s\in S} d_G(w)=|S|d_G(w)$, where the inequality holds by the problem assumption.

Putting everything together, $|S|>|S|$, a contradiction.

Improvement/suggestion is much appreciated!