# 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)

-

## 1 Answer

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.

-
{"extraction_info": {"found_math": true, "script_math_tex": 0, "script_math_asciimath": 0, "math_annotations": 0, "math_alttext": 0, "mathml": 0, "mathjax_tag": 0, "mathjax_inline_tex": 30, "mathjax_display_tex": 3, "mathjax_asciimath": 0, "img_math": 0, "codecogs_latex": 0, "wp_latex": 0, "mimetex.cgi": 0, "/images/math/codecogs": 0, "mathtex.cgi": 0}, "config": {"markdown_headings": true, "markdown_code": true, "boilerplate_config": {"ratio_threshold": 0.18, "absolute_threshold": 10, "end_threshold": 15, "enable": true}, "remove_buttons": true, "remove_image_figures": true, "remove_link_clusters": true, "table_config": {"min_rows": 2, "min_cols": 3, "format": "github"}, "remove_chinese": true, "remove_edit_buttons": true, "extract_latex": true}, "english_confidence": 0.9464388489723206, "perplexity_flag": "head"}