How can we prove the following conjecture?


Given any simple unweighted bipartite graph $G(V\_1, V\_2, E)$, there always exists a subgraph $G'(V\_1, V\_2, E')$ of $G$ such that the two following conditions are simultaneously satisfied:


1) $|E'| \ge \frac{1}{2}|E|$ .


2) The degree of each vertex in $G'$ is at most half of the maximum vertex degree $d^{\max}\_G$ in $G$ (for the sake of simplicity assume $d^{\max}\_G$ is an even integer).



Existence of bipartite subgraphs satisfying degree and edge cardinality constraints
If $d\_G^{\max}$ is odd and the graph is regular, this clearly is not possible. But if $d\_G^{\max}=2k$ is even, this is possible: the edges may be properly colored with $2k$ colors [this is well-known bipartite variant of Vizing's theorem, which may be proved, for example, by induction in number of edges: color all edges except the edge $uv$, there are free colors for vertices $u,v$ --- call them 1,2. There can not exist a 1-2 chain from $v$ to $u$ since it would produce an odd cycle in $G$. Thus interchange 1 and 2 in the $u$-component of the graph formed by edges of colors 1,2, after that $uv$ may be colored with 2.] Now take $k$ most popular colors. 


