Matching in a bipartite graph with classes $A$ and $B$ and $d(a) \geq 1$ for all $a \in A$. And $d(a) \geq d(b)$ for all $(a,b) \in E(H)$

Question

Let $H$ be a bipartite graph with classes $A$ and $B$. Further we have that $d(a) \geq 1$ for all $a \in A$. And $d(a) \geq d(b)$ for all $(a,b) \in E(H)$.

I want to show that $H$ contains a matching that covers the vertices of $A$. Therefore, I want to apply Halls Theorem i.e. I want to show that $|N(S)| \geq |S|$ for all $S \subseteq A$.

Now for a contradiction I suppose that this does not hold i.e. there exists a subset $S \subseteq A$ such that $|N(S)|<|S|$. Now my goal would be to show that there is a contradiction to the initial assumption $d(a) \geq d(b)$. Do you see a way to get a contradiction?

Answer 1

The reasoning is somewhat longer than I first thought.

So let $H$ be a bipartite graph with parts $A$ and $B$. If $A$ has no isolated vertices and for any adjacent vertices $a\in A$ and $b\in B$ the inequality $\operatorname{deg}(a)\geq\operatorname{deg}(b)$ is satisfied, then $H$ contains a matching that covers the vertices of $A$.

Let us first prove a simple lemma.

Lemma. Let $H$ be a bipartite graph with parts $A$ and $B$. If $S\subset A$, then $$ \sum_{a\in S}\operatorname{deg}(a)\leq\sum_{b\in N(S)}\operatorname{deg}(b), \tag1 $$ where $N(S)$ is the set of neighbors of vertices from $S$.

Proof. In an induced bipartite graph $G$ on vertices $S\cup N(S)$ the equality $$ \sum_{a\in S}\operatorname{deg}_G(a)=\sum_{b\in N(S)}\operatorname{deg}_G(b) $$ is true. Since $\operatorname{deg}_G(a)=\operatorname{deg}(a)$ and $\operatorname{deg}_G(b)\leq\operatorname{deg}(b)$, it follows that $(1)$ is satisfied and our lemma is proved.

Let us prove that for any $S\subset A$ the inequality $|S|\leq|N(S)|$ holds.

We proceed by induction on the number of vertices in $S$. If $|S|=1$, then our statement is obvious and our induction starts.

Let us choose an arbitrary vertex $v\in S$. Let $S'=S\setminus\{v\}$. By the inductive hypothesis $|S'|\leq |N(S')|$. Consider two cases: 1) $|S'|<|N(S')|$, 2) $|S'|=|N(S')|$.

1. If $|S'|<|N(S')|$, then $|S|=|S'|+1\leq|N(S')|\leq|N(S)|$.

2. If $|S'|=|N(S')|$, then in the induced graph $S'\cup N(S')$ the Hall condition is satisfied and hence by Hall's theorem there exists a matching that covers the vertices of $S'$. Let $S'=\{a_1,\ldots,a_k\}$, $N(S')=\{b_1,\ldots,b_k\}$, and $e_i=\{a_i,b_i\}$ ($1\leq i\leq k$) be the edges of this matching.

On the one hand, by the lemma we have $$ \sum\operatorname{deg}(a_i)\leq \sum\operatorname{deg}(b_i).\tag2 $$

On the other hand, by the condition $\operatorname{deg}(a_i)\geq\operatorname{deg}(b_i)$ for each $i$ and hence $$ \sum\operatorname{deg}(a_i)\geq \sum\operatorname{deg}(b_i).\tag3 $$ From $(2)$ and $(3)$ it follows that $$ \sum\operatorname{deg}(a_i)=\sum\operatorname{deg}(b_i).\tag4 $$

If $N(v)\subset N(S')$, then by the lemma we get $$ \sum\operatorname{deg}(a_i)+\operatorname{deg}(v)\leq \sum\operatorname{deg}(b_i) $$ Since $\operatorname{deg}(v)>0$, this last inequality contradicts $(4)$.

It follows that $N(v)\not\subset N(S')$. Then $|N(S)|>|N(S')|\geq|S'|$, so $|N(S)|\geq|S'|+1=|S|$.

Answer 2

Start by thinking on a set with two vertices, $a_1,a_2$.

Lets assume that they are indeed connected only to one vertex $b$.

(This is the only option for them not behaving nicely because $d(a)\geq 1$.

Now, we know that $d(b)\leq d(a)$, but also that $d(b) = 2$. So from the second property of $d(b)\leq d(a_1),d(a_2)$ you will conclude that the degree of both $a_1,a_2$ has to be at least 2, so, you will need to add two more vertices to the set of neighbors of $a_1,a_2$, lets mark them as $b_1,b_2$ and therefore $N(\{a_1,a_2\})=\{b,b_1,b_2\}$, so you got yourself a contradiction.

Now try to think how you can generalize it to bigger sets!