# It is possible to partition the vertex set of a graph $V=V_1\cup V_2$ so that …

so that at most half of all edges run within each part. This is seen by, for example, http://math.stackexchange.com/a/210609/44285

I am also asked to show that in addition to the above, one may also demand that each $V_i$ span at most a third of all the edges. Anyone got any ideas?

-