Let H be a maximum bipartite subgraph of G. The bipartition divides the vertices of H (and G) into two sides, L and R. Prove that every vertex v has the property that (according to G) at least half of its incident edges go across to the other side.
So among all spanning subgraphs, the one which has the maximum number of edges is the maximum bipartite subgraph. But I have little idea of how to start this proof, is it related to number of edges of H being at least half the size of G?