Proof bipartite graph matching

Question

Let $G = (V, E)$ be a bipartite graph with bipartition $V = A \sqcup B$. Assume that $\delta(G) \geq 1$, and that $\deg(a) \geq \deg(b)$ for every edge $\left\{a, b \right\} \in E $ with $a \in A$. Show that $G$ contains a matching of $A$, i.e. a matching that meets every vertex of $A$.

I tried using Hall's marriage theorem and Stable marriage theorem (the two we've been taught) but I'm getting stuck.

Answer 1

Hint:

• Put on each edge $e = \{a,b\}$ a token of value $\frac{2}{\deg(a) + \deg(b)}$.
• For any set $X \subseteq A$, $X$ is incident to edges of total token value of at least $|X|$.
• For any set $Y \subseteq B$, $Y$ is incident to edges of total token value of at most $|Y|$.

I hope this helps $\ddot\smile$