1
$\begingroup$

There is a bipartite graph $G=(A,B,E)$ such that for every edge $(a,b)$ (where $a$ comes from $A$ and $b$ from $B$), $\deg(a) \geq \deg(b)$, and additionally $\deg(a) \geq 1$ for all $a \in A$. From this, how can I prove there is matching which covers all of $A$?

$\endgroup$
2
  • 2
    $\begingroup$ Have you tried using Hall's criterion? $\endgroup$ Feb 25 '16 at 16:01
  • $\begingroup$ Yes, withous success so far. $\endgroup$
    – Nelson
    Feb 25 '16 at 16:12
1
$\begingroup$

Hint: Use Hall's criterion.

In more detail, suppose that Hall's criterion didn't hold. Choose a set $X$ of minimal size satisfying $|N(X)| < |X|$. Show that $X$ is not empty, and let $Y = X \setminus \{x\}$ for some arbitrary $x \in X$. Show that $Y$ has a perfect matching with $N(Y)$, and prove that $N(N(Y))=Y$ by counting the edges connecting $Y$ and $N(Y)$ in two ways. Show that $\emptyset \neq N(x) \subseteq N(Y)$, and reach a contradiction.

$\endgroup$

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.