# Graph Theory - Matching

Hi I'm trying to prove

Let $G$ be bipartite graph with bipartition $\{A,B\}$. Assume that $\delta(G)\geq1$, and that $d(a)\geq d(b)$ for every edge $ab$ with $a \in A$. Show that $G$ contains a matching of $A$.

I turned in an initial idea of trying to show Hall's Theorem/Condition, but it didn't seem to be correct. Can someone tell me what I should be doing? Thanks!

Let $S$ be an arbitrary subset of $A$, and let $E_S$ denote the set of all edges of the graph with one endpoint in $S$. Then we have $$|S| = \sum_{ab \in E_S} \frac1{\deg(a)} \le \sum_{ab \in E_S} \frac1{\deg(b)} \le |N(S)|$$ where the inequality in the middle follows from the rule that $\deg(a) \ge \deg(b)$ for all edges $ab$, and evaluating the sums is a bit of counting-in-two-ways black magic that deserves to be stared at for a minute or two.
(Note: notation-wise, I'm assuming that for an edge $ab \in E_S$, $a$ is the endpoint in $A$ and $b$ is the endpoint in $B$.)
• The first one (on the $|S|$ side) is easier to start off with: think about how many $\frac1{\deg(a)}$ terms you'll get in total for each vertex $a \in S$. Once you figure that out, you can think about why it becomes an inequality on the $|N(S)|$ side. – Misha Lavrov Feb 17 '18 at 19:48