= Solution
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$ gives
$$
\mathbb P(I_e=1)=2\left(\frac12\right)\left(\frac12\right)=\frac12.
$$
Because $X=\sum_{e\in E(G)}I_e$, <linearity of expectation> gives
$$
\boxed{\mathbb E X=\sum_{e\in E(G)}\mathbb E I_e=\frac m2.}
$$
Some realization therefore has $X\geq 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$,
$$
\mathbb P(u\in U,v\notin U)
=\frac{n/2}{n}\frac{n/2}{n-1},
$$
and the reverse orientation has the same probability. Thus
$$
\mathbb P(I_{uv}=1)=\frac{n}{2(n-1)}.
$$
Another application of <linearity of expectation> gives
$$
\mathbb E X=\frac{mn}{2(n-1)}.
$$
At 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>.
Back to article page
