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>



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


