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?
