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).
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.
