3
$\begingroup$

Let $G$ be a bipartite graph, with bipartition $(X,Y)$ with no isolated vertices. Suppose that for every edge $xy$ with one end $x\in X$ and another end $y\in Y$, we have $\deg(x) \ge \deg(y)$. Prove that $G$ has a matching that covers $X$.

I think I am supposed to apply Hall's Theorem here? The problem is, how would I show that $|N(X)| \ge |X|$ where $|N(X)|$ is the set of neighbours of the vertices of $X$.

$\endgroup$
8
$\begingroup$

$$ |X|=\sum_{\langle x,y\rangle\in E}\frac1{\deg(x)}\le\sum_{\langle x,y\rangle\in E}\frac1{\deg(y)}=|Y|\;. $$

$\endgroup$
  • $\begingroup$ Sorry, how did you come up with the formula, $$\sum_{\langle x,y\rangle\in E}\frac1{\deg(y)}=|Y|\;. $$ $\endgroup$ – Heisenberg Oct 18 '12 at 14:24
  • $\begingroup$ @Heisenberg: Do you literally mean how I came up with it, or how it can be proved? Every $y\in Y$ occurs $\deg(y)$ times in the sum and so contributes $\deg(y)/\deg(y)=1$. How I came up with it is hard to say; I think I thought something along the lines that if we want to compare the sets then we should count them using the edges because that's what links them, and then we have to divide by the degrees to avoid overcounting, and then I saw that we can use the given inequality to go from dividing through the one degree to dividing through the other degree. $\endgroup$ – joriki Oct 18 '12 at 14:31

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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