# Let $G=(V=X \cup Y,E)$ be a bipartite graph.Show that G has a matching which matches every vertex of X.

I have a similar question to this on my test tomorrow. Any help towards this question will help

Let $G=(V=X \cup Y,E)$ be a bipartite graph. Suppose that the degree of each vertex d(v)≥1. Assume also that for each edge xy with x∈ X, we have d(x)≥d(y). Show that G has a matching which matches every vertex of X.

Hint. It is enough to show that Hall's condition holds on the X-side, since if a matching has an unmatched X-vertex, we can then use our algorithmic proof of Hall's Theorem to make it larger (and saturating one extra vertex of X)

-

We want to show that for every $S \subseteq X$, $\lvert N(S) \rvert \geq \lvert S \rvert$, where $N(S)$ denotes the neighborhood of $S$.
Let $S \subseteq X$ be a minimal counterexample. This means that for every $x \in S$, $S \setminus \{x\}$ satisfies Hall's condition. Choose $x \in S$ and let $S' = S \setminus \{x\}$.
First, we may assume that $N(x) \subseteq N(S')$. If not, let $y$ be a neighbor of $X$ not in $N(S')$. Then, by hypothesis, we may match all of the elements of $S'$ to elements of $N(S')$ and may also match $x$ to $y$. Furthermore, we may assume that $\lvert N(S') \rvert = \lvert S' \rvert$: otherwise, we have $$\lvert N(S) \rvert \geq \lvert N(S') \rvert \geq \lvert S' \rvert + 1 = \lvert S \rvert.$$ Now we match every element $z$ of $S'$ to an element $y$ of $N(S')$. By our hypothesis that $d(z) \geq d(y)$, we have $$\sum_{y \in N(S')} d(y) \leq \sum_{z \in S'} d(z) \leq \bigl\lvert E\bigl(S', N(S')\bigr) \bigr\rvert \leq \sum_{y \in N(S')} d(y),$$ that is, $$\sum_{y \in N(S')} d(y) = \bigl\lvert E\bigl(S', N(S')\bigr) \bigr\rvert.$$ This means that all of the neighbors of the elements of $N(S')$ are in $S'$, which contradicts our hypothesis that $d(x) \geq 1$. Hence, $S$ cannot be a counterexample, and $X$ satisfies Hall's condition.