Show that we can choose bipartite subgraph Given the graph:
$$G = (V,E) \quad |V| = 2n, \quad |E| = m $$
Prove that in the graph $G$ we can choose a bipartite subgraph $G' = (V',E')$ with $ |E'| \geq  \frac{mn}{2n - 1} $
I guess I have to use a random graph to prove the statement. 
But what is the first step?

Your instinct is correct.  Consider a uniformly random partition of $V$ into two sets of size $n$.  Show that for each edge $e \in E$, $$\mathbb{P}(\text{the endpoints of $e$ are in different sets}) = \frac{n}{2n-1}.$$  Then use linearity of expectation.
