Suppose $G$ is a (simple) graph. A set of edges $M\!\subseteq\!E(G)$ is a matching if \forall e,e'\!\in\!M: $e$ and e' have no common vertex. A graph $H$ is bipartite if $\exists A,B\!\subseteq\!V(H)$ such that $A\cap B=\emptyset$, $V(H)=A\cup B$, and every edge in $H$ has one vertex in $A$ and one in $B$. A set of vertices $A\subseteq V(G)$ is an anticlique (i.e. "empty subgraph") if there are no edges in $G$ between vertices of $A$. Denote $n:=|V(G)|$ and $m:=|E(G)|$.
How can I prove the next statement:
PROBLEM: if $G$ has a matching with $k$ edges, then it has a bipartite subgraph $H$ with at least $(|E(G)+k|)/2$ edges.
Attempt of proof 1: I tried this with induction on $k$.
$k=m:$ this means that $G$ is bipartite, so $H:=G$ suffices. $\checkmark$
$m,\ldots,k\rightarrow k\!-\!1:$ Induction hypothesis: suppose we have a matching with $k-1$ edges in $G$ and suppose the claim is true for all matchings with at least $k$ edges. I don't know how to find an additional edge to add to the $(k-1)$-matching...
Attempt of proof 2: I have a very strong hunch this was meant to be solved via the probabilistic method (it was posted in the Probabilistic Method pack of problems). It would suffice to prove that if we randomly choose two anticliques $A,B\subseteq V(G)$, that the expected number of edges between $A$ and $B$ is $\mathbb{E}(|E[A,B]|)=(|E(G)+k|)/2$. It would then follow that there exists a choice of $A,B$ that has more than $(|E(G)+k|)/2$ edges. But I think randomly choosing any two anticliques will not suffice to get such a high expected value. Moreover, I don't know how to use the hypothesis about the existence of a $k$-matching...
any hints are very welcome