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.