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

1 Answers 1

8

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

  • 0
    @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.2012-10-18