Random cut lower bound

Every finite graph with $m$ edges has a cut of a graph of size at least $m/2$, and hence a spanning bipartite graph with at least $m/2$ edges. Put each vertex independently on either side with equal probability. Every edge crosses with probability $1/2$, so linearity of expectation gives expected cut size $m/2$.

If a graph has even order $n$ and $m$ edges, it has a cut with equally sized parts and at leastcrossing edges. Choose one part uniformly among the $n/2$-vertex subsets. A fixed edge is separated with probabilityand apply linearity of expectation.