Balanced random cut lower bound
= Balanced random cut lower bound
If a graph has even order $n$ and $m$ edges, it has a cut with equally sized parts and at least
$$
\frac{mn}{2(n-1)}
$$
crossing edges. Choose one part uniformly among the $n/2$-vertex subsets. A fixed edge is separated with probability
$$
2\frac{n/2}{n}\frac{n/2}{n-1}=\frac{n}{2(n-1)},
$$
and apply <linearity of expectation>.