4
$\begingroup$

We all know Hall's marriage theorem as following:

A bipartite graph $G$ with bipartition $\{ A,B \}$ contains a matching of $A$ if and only if $|N(S)|\geq |S|$ for all $S\subseteq A$.

And I am thinking about a generalized theorem of it.

A bipartite graph $G$ with bipartition $\{ A,B \}$ contains a $k$-matching of $A$ if and only if$|N(S)|\geq k|S|$ for all $S\subseteq A$. (A $k$-matching means a subgraph $G'$ of $G$ which $A\subseteq G'$ and $d_{G'}(A_i)=k$ and for $i\neq j$, $neighbor(A_i) \cap neighbor(A_j)=\varnothing$)

Is it right? How to prove?

See a math.SE post: https://math.stackexchange.com/questions/1481389/a-generalized-theorem-of-halls-marriage-theorem

$\endgroup$
  • 1
    $\begingroup$ This is usually known as the polygamous version of Hall's Marriage Theorem, if I'm not mistaken. $\endgroup$ – Patrick Stevens Nov 30 '15 at 15:38
9
$\begingroup$

Yes, it is right. Just consider $k$ copies of each vertex in $A$ and apply usual Hall theorem to the new graph.

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