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

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

1 Answer 1

Reset to default
11
$\begingroup$

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

Improve this answer
$\endgroup$

You must log in to answer this question.