Let $G=(L,R,E)$ be a bipartite connected graph. I wish to prove that $G$ has a matching for all vertices of the left side $L$, assuming I know that for every edge $\left(l_i , r_j \right)$ that deg$\left( l_i \right) \geq$deg$\left( r_j \right)$.
Intuitively, I want to show how I can construct (possibly, by induction) a matching for all vertices of the side $L$. For a single vertex, it is obvious. But I'm having a bit trouble for the induction step, which got me thinking – maybe there is a simpler way than by induction?
Edit: By induction, I mean induction on the number of vertices of the left side $L$.
Best Answer
Let $L'$ be any subset of $L$. Let the vertices of $L'$ and $N(L')$ be $l_1,l_2,...,l_n$ and $r_1,r_2,...,r_m$, respectively, arranged in increasing order of valency.
$l_1$ is adjacent to at least one $r_i$ and so $\rho(l_1)\ge\rho(r_1)$. Now suppose $\rho(l_i)\ge\rho(r_i)$ for $1\le i\le k<n$. Then $$\sum_1^{k+1}\rho(l_i)>\sum_1^{k}\rho(r_i)$$ and so there is an edge incident with an $l_x$ and an $r_y$, where $x\le k+1$ and $y>k$. Then $$\rho(l_{k+1})\ge \rho(l_{x})\ge \rho(r_{y})\ge \rho(r_{k+1}).$$ Hence, by induction, $\rho(l_i)\ge\rho(r_i)$ for $1\le i\le n$ and, in particular, $n\le m$. Therefore, by Hall's Marriage Theorem, there is a matching for $L$.