Random cut lower bound
= 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$.