Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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)

share|improve this question

1 Answer 1

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.

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.