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)$ 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?
 A: 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')|$.

*

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


*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|$.
A: 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!
