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](http://www.artofproblemsolving.com/Forum/viewtopic.php?f=42&t=137128).


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?



Condition on a bipartite graph to have an $m$-factor
Take the general Ore-Ryser theorem:


Let $G$ be bipartite graph with vertex set $V=X\coprod Y$ ($X$, $Y$ parts) and $f:V\rightarrow \{0,1,2,\dots\}$ be a function such that $f\left(x\right)\leq\left(\text{degree of }x\right)$ for every $x\in X$. Then there exists a subgraph of $G$ (obtained from $G$ by removing some edges, not vertices), for which $f$ is degree function, if and only if for any $Y\_1\subset Y$ one has 
$$
\sum\_{y\in Y\_1} f(y)\leq \sum\_{x\in X} \min(f(x),d\_{Y\_1}(x)), 
$$
and this becomes an equality for $Y=Y\_1$ (not necessarily only for $Y=Y\_1$). Here, $d\_{Y\_1}(x)$ denotes the number of neighbors of $x$ in $Y\_1$.


If $f(v)\equiv m$, it is easy to verify that we get your problem (or, strictly speaking, we get that one has a $m$-regular subgraph, but it is well known that it factors onto $m$ 1-regular subgraphs). 


And the Ore-Ryser theorem may be proved by easy induction, the same as is used for the Hall marriage problem. Either there exists some nonempty $Y\_1\ne Y$, for which the equality occurs, then we apply the induction propose for $X$ and $Y\_1$ (with $f$ changed on $X$ to $\min(f,d\_{Y\_1})$) and then to $X$ and $Y\setminus Y\_1$. Or we have strict inequalities for all nonempty $Y\_1\ne Y$, then take any edge $xy$, remove it and replace $f(x)$ to $f(x)-1$, $f(y)$ to $f(y)-1$.


