# A generalized theorem of Hall's marriage theorem

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?

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

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