Skip to main content
2 of 3
added 2 characters in body
user avatar
user avatar

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?

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

user79942