Using a greedy algorithm to find a cut S which at least half of the edges cut
List the vertices in some order, $v_1,\ldots,v_n$. Put $v_1$ in an arbitrary side of the cut. For each of the vertices $v_2,\ldots,v_n$, put it in the side of the cut which maximized the number of edges cut (only counting edges involving vertices which have already been processed). Since there are only two sides, each time you cut at least half the edges.