 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$.