This might be the most stupid question I am ever posting here: I am asking for a proof or a counterexample to a problem I proposed on MathLinks long ago.

Let $G$ be a bipartite graph, i. e., a graph such that the set of its vertices is the union of two sets $A$ and $B$, and each edge of the graph $G$ connects a vertex from $A$ with a vertex from $B$. For every subset $U$ of $A$ and every integer $k$, let $N_{k}\left(U\right)$ denote the set of all vertices from $B$ which have at least $k$ neighbours in the set $U$. Assume that $\left|A\right|=\left|B\right|$.

Some matchings of $G$ are called *disjoint* if there is no edge common to two or more of these matchings.

Let $m$ be a positive integer. Prove or disprove that the graph $G$ has $m$ disjoint perfect matchings if and only if the inequality $\left|N_{1}\left(U\right)\right|+\left|N_{2}\left(U\right)\right|+...+\left|N_{m}\left(U\right)\right|\geq m\left|U\right|$ holds for every subset $U$ of $A$.

Note that probably the assumption $\left|A\right|=\left|B\right|$ can be dropped if we replace "perfect matchings" by "$A$-complete matchings" (i. e., every vertex of $A$ is matched in every of these matchings). Also note that the "only if" direction is easy. Finally, of course, for $m=1$, this is Hall's marriage theorem.

The fact that I have posted the above problem on MathLinks in 2007 speaks for it being easy, but the fact that I have always been too lazy to write up my solution speaks for it being wrong. I have tried the obvious induction approach now, but I fail to obtain a reasonable inequality for $m-1$ instead of $m$ after deleting the first perfect matching. Any ideas?

Disjoint matchings of graphs, Journal of Combinatorial Theory, Series B, Volume 22, Issue 3, June 1977, Pages 207--210, sciencedirect.com/science/article/pii/0095895677900661 . – darij grinberg Aug 13 at 12:07