2
$\begingroup$

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!

$\endgroup$
1
$\begingroup$

Hall's theorem is indeed the way to go here, but trickery must be employed.

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

$\endgroup$
  • $\begingroup$ Can you explain a little more on the ends of that inequality. I've been staring at it, but I can't come up with a strong convincing argument for why it's true. $\endgroup$ – TurtleHerald Feb 17 '18 at 18:37
  • $\begingroup$ 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. $\endgroup$ – Misha Lavrov Feb 17 '18 at 19:48

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.