A certain bipartite graph has a matching

Question

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

Answer 1

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

Answer 2

Let us denote the property you mentioned ($\forall (li,rj)\in E:\deg(li)≥\deg(rj)$) by $P$.

Claim:
Let $n\in \mathbb{N}$ and $G=(L,R,E)$ be a bipartite graph with the property $P$ such that $|L|=|R|=n$ and there are no isolated vertices in $L$, then neighboring vertices in $G$ have the same degree.

Assume the claim was true, and let $G=(L,R,E)$ be a connected bipartite graph with the property $P$, let $L'\subseteq L$ and define $R':=N_G(L')$. Assume towards contradiction that $|L'|>|R'|$, thus there exists $L''\subset L'$ such that $N_G(L'')=R', |L''|=|R'|$ and notice that the graph $G'=(L'',R',E')$ where $E'$ are the edges between $L''$ and $R'$ has the property $P$ and that there aren't any isolated vertices in $G'$.
Using the claim, we conclude that neigboring vertcies in $G'$ have the same degree, but there is a $v\in L'/L''$ which has a neighbor $u\in R'$ which has a neighbor $w\in L''$, violating the property $P$ - a contradiction.
We got that for every $L'\subseteq L:|L'|\le|N_G(L')|$, and by Hall's marriage theorem, we conclude that there is a matching that matches all of the vertices in $L$.

Proof of the claim:
By (strong) induction on $n+\delta$, where $\delta$ is the lowest degree in $L$.
For $n+\delta=2$, i.e., $n=1,\delta=1$ the claim is obvious.
Let $\delta \le n \in \mathbb{N}$ and assume the claim holds for every $\delta' \le n'$ such that $\delta' + n' < \delta + n$.
If $\delta=1$, then we have $v\in L, u\in R$ such that $(u,v)\in E$ and by $P$ we have that $\{u,v\}$ is a connected component as $u$ may not have any more neighbors. We can use the induction hypothesis on $G'=(L/\{v\},R/\{u\}, E/\{(u,v)\})$ and we are done.

Othwerwise ($\delta \ge2)$, we can easily show using the induction hypothesis that $\forall L'\subseteq L:|L'|\le |N_G(L')|$, similarly to the way we have proven the original statement using the claim, but using the induction hypothesis instead.
We conclude that there exists a perfect matching in $G$ and if we remove its edges we get a graph $G'=(L,R,E/M)$ (where $M$ is the set of edeges in the perfect matching) with no isolated vertices in $L$ (as $\delta \ge 2$) with $\delta'=\delta - 1$ and $n'=n$, so we may use the induction hypothesis and we are done.

$$\square$$

Edit:
I've been asked to justify the existence of a set $L''\subset L'$ such that $N_G(L'')=R'$ and $|L''|=|R'|$.
We can convince ourselves by observing this simple algorithm:

Set $A:=R',L''=\phi$.
While $A \neq \phi$:
Pick an arbitrary vertex $u\in A$ and take a vertex $v\in L'/L''$ such that $(u,v)\in E$.
Set $L'' \leftarrow L''\cup \{v\},A\leftarrow A/N_G(v)$

In words, at each step we choose a new vertex $u$ from $R'$ which we have not yet "reached" from our set $L''$, we take a vertex from $L'/L''$ that is adjacent to it (indeed, one must exist as no vertex in $L''$ is adjacent to $u$) and add it to $L''$, thus reaching at least one new element in $R'$.
As we add only one vertex to $L''$ at each iteration and remove at least one element from $R'$, we have that $|L''| \le |R'|$. We can now add arbitrary vertices from $L'$ until the sizes match exactly.