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?
every vertex $v$ has the property that (according to $G$) at least half of its incident edges go across to the other side.
Yes, otherwise we can swap $v$ to the other side of the bipartition and connect it in $H$ with exactly these vertices of its opposite side to which $v$ is adjacent in $G$. This will increase the number of edges in $H$, violating its maximality. So there is no such $v$, which implies, in particular, that a number of edges of $H$ is at least a half of a number of edges of $G$
So among all spanning subgraphs, the one which has the maximum number of edges is the maximum bipartite subgraph.
I don’t understand what this means. The spanning subraph of $G$ with the maximum number of edges clearly is $G$.
