I found this problem in the excellent book of Laszlo Lovasz - "Combinatorial Problems and Exercises"- chapter 7, problem 18. The solution is based on a result of O.Ore-D.Gale-H.J.Ryser, which is given as a separate problem in the same book. If $f(v)$ is an integer valued function on $V(G)$ and we can delete some edges of $G$, so that the degree of $v$ with respect to the new graph is $f(v)$, then we say that $G$ has a f-factor. Claim $(1)$. Let $G$ is a bipartite graph, with bipartition $A,B$. $f(v)$ is integer valued function on $V(G)$. Then $G$ has a f-factor if and only if : $(i)\,\,\,\,\,\,\,\,\,\, \sum_{v\in A}f(v) = \sum_{v \in B} f(v)$. $(ii)\,\,\,\,\,\,\,\,\,\, \sum_{v \in X} f(v) \leq m(X,Y) + \sum_{v \in B-Y} f(v)$, $\, \forall X,Y; \, X \subset A,\, Y \subset B$ where $m(X,Y)$ means the number of edges connecting $X$ with $Y$. Now, $(1)$ is applied to the complementary bipartite graph of that given in the problem statement. Proof of $(1)$ involves Max-flow-min-cut theorem, which involves the Menger's theorem. So, this seemingly easy problem involves some deep results in the graph theory.

I was very interested in this problem and the solution given by dgrozev and was disappointed to find that the theorem and proof involved are inaccessible. Is there anyone kindly post a more elementary solution and/or online accessible references of those theorems involved? By the way, I and my colleague are trying to solve this by means of marriage theorem. We found that the problem is equivalent to the following statement; Let $d < \frac{n}{2}$ be non-negative integers. Suppose that a bipartite graph $G$ are partitioned into two part $A$ and $B$ with equal number of vertices (with the only edges connecting vertices of $A$ with those of $B$). If the minimal degree of vertices is $n-d$, then there is a regular bipartite subgraph of $G$ with degree $n-2d$. By marriage theorem, we have the following lemma; Suppose that a bipartite graph $G$ are partitioned into two part $A$ and $B$ with equal number of vertices. If the minimal degree is no less than $\frac{n}{2}$, then there exists a perfect matching. Applying the lemma one can easily obtain the result for $d$ is maximal integer less than $\frac{n}{2}$. At my opinion, one may proceed using induction somewhere but I don't know how to do.

Now I have cut the "max-flow-min-cut theorem" and related theorems from the book mentioned above. I'm still looking forward to see shorter and direct solution.

Attachments:
max-flow-min-cut.pdf (93kb)

Good job! There are many other applications of Max-flow-min-cut (or Ford-Fulkerson) theorem. For example, Hall marriage theorem may be proved with 2 lines - the same idea as in the proof of Theorem 3 (Ore-Gale-Ryser). No wonder, because that theorem generalizes the Hall marriage thm. Indeed, when the factor function $f\equiv 1$ the condition of thm 3 is equivalent to the Hall's condition.