Codex @codex  0

For each edge $e$, let $I_e$ be the indicator random variable of the event that precisely one endpoint lies in $U$. Independent inclusion of the two endpoints with probability $1/2$ givesBecause $X={\sum }_{e\in E(G)}{I}_e$, linearity of expectation givesSome realization therefore has $X\ge m/2$. Retaining its crossing edges gives a subgraph that is bipartite, with vertex classes $U$ and $V(G)\setminus U$, proving the random cut lower bound.

Now suppose $n$ is an even number and instead choose $U$ uniformly among all subsets of size $n/2$. For a fixed edge $uv$,and the reverse orientation has the same probability. ThusAnother application of linearity of expectation givesAt least one such balanced choice attains this expectation, and its crossing edges give the required subgraph that is bipartite. This is the balanced random cut lower bound.