If a Graph G has $n$ vertices and $e$ edges, show that it contains a bipartite subgraph with at least $\frac{en}{2(n-1)}$ edges.
I tried to consider the following probability space: Let A be selected at random from all $\frac{n}{2}$ sized subsets of the vertex set. Let B = V $\setminus$ A. What is the probability that edge $(x,y)$ has either $x$ or $y$ in A but not both?
I figured it out. Let $X_{x,y}$ be the event that $(x,y)$ crosses. Then, Pr[$X_{x,y}$] = $\frac{ {\frac{n}{2}\choose1} \times {\frac{n}{2}\choose1}}{n\choose2}$ = $\frac{n}{2(n-1)}$. This is because we count the number of ways to pick $x \in A$ and $y \in B$ or $y \in A$ and $x \in B$. We then divide by the total number of ways to pick x and y from $V$.
By linearity of expectation over all edges $e$, $E[X = \sum_{(x,y)\in E}X_{x,y}]$ = $\frac{en}{2n-1}$. Therefore, there exists such a bipartite subgraph.