5
$\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
  • 1
    $\begingroup$ This is usually known as the polygamous version of Hall's Marriage Theorem, if I'm not mistaken. $\endgroup$ Nov 30, 2015 at 15:38

1 Answer 1

11
$\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 and acknowledge you have read our privacy policy.