Graph partition that span a third of edges Given a graph G is easy to see that we have a partition $V=V_1 \cup V_2$ so that 
$$e(G[V_1])+e(G[V_2])\leq e(G)/2$$. How can we improve this result showing that we can choose $V_i$ such that $e(G[V_i])\leq e(G)/3$ for $i=1,2.$
 A: 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)$.
A: Take a bipartition $V=V_1\cup V_2$ such that this sum $e(G[V_1])+e(G[V_2])$ is minimal. Consider a vertex $v\in V_i\subset V$, denote $d_{in}(v)$ be the degree of $v$ in the subgraph $V_i$, and $d_{out}(v)$ be the number of edges joining $v$ and a vertex in $V_{i+1}$ (Here, indices are modulo $2$). Observe that $d(v)=d_{in}(v)+d_{out}(v)$.
We claim that $d_{in}(v)\le d_{out}(v)$ for every vertex $v$ in this partition. Otherwise,   suppose some vertex $v\in V_1$ has $d_{in}(v) > d_{out}(v)$, then consider a new partition $V=V'_1\cup V'_2$ with $V'_1=V_1-\{v\}$ and $V'_2=V_2+\{v\}$, then
\begin{equation*} 
\begin{split}
e(G[V'_1])+e(G[V'_2]) 
& =(e(G[V_1])-d_{in}(v))+(e(G[V_2])+d_{out}(v)) \\ 
& <e(G[V_1])+e(G[V_2])
\end{split}
\end{equation*}
which contradicts the choice of $V_1$ and $V_2$. Likewise, this claim holds for any $v\in V_2$. Now we count the number of edges. Note that for all $v\in G$, $d_{in}(v)\le \frac{1}{2}d(v)$ by the claim, so
$$
e(G[V_1])+e(G[V_2]) =\sum_{v\in G}d_{in}(v)
\le \frac{1}{2}\sum_{v\in G}d(v)
= \frac{1}{2}e(G)
$$ Moreover, observe that the number of edges joining $V_1$ ad $V_2$ is $$e(G)-e(G[V_1])-e(G[V_2])= \sum_{v\in G[V_1]}d_{out}(v)\ge \sum_{v\in G[V_1]}d_{in}(v)=2e(G[V_1])$$ So since $e(G[V_2])\ge 0$, we have $3e(G[V_1])\le e(G)$. The same holds for $e(G[V_2])$ analogously. $\blacksquare$
