Graph partition that span a third of edges

Solution 1:

Let $V_1,V_2$ be a bipartition of $V$ that maximizes the number $t$ of edges between $V_1$ and $V_2$. For a vertex $v$ define the internal degree $d_i(v)$ as the degree of $v$ in its partite set and the external degree $d_e(v)$ as the degree of $v$ to the other partite set. Clearly $d(v)=d_i(v)+d_e(v)$.

We have $d_i(v)\leq d_e(v)$: indeed, if $d_i(v)>d_e(v)$ we can move $v$ to the other partite set and get a bipartition of $V$ with more edges between the partite sets. Contradiction.

Also note that $e(G[V_1])+e(G[V_2])+t=e(G)$ (*).

The only thing left to do is to count edges. We may assume $e(G[V_1])\leq e(G[V_2])$. Then $e(G[V_1])\leq e(G[V_2])=\frac12\sum_{v\in V_2}d_i(v)\leq\frac12\sum_{v\in V_2}d_e(v)=\frac12 t$.

Now assuming that $e(G[V_2])>\frac13e(G)$ would imply that $t>\frac23e(G)$, contradicting (*).

We conclude that $e(G[V_1])\leq e(G[V_2])\leq\frac13e(G)$.