How many edges in a tripartite subgraph? Suppose that you have a graph, $G$. $G$ must have a subgraph, $H$ such that $H$ is tripartite and contains at least $\frac{2}{3}e(G)$.
I'm not even sure where to begin proving this. Any help would be greatly appreciated.
 A: We use a probabilistic approach (see, for instance, “The probabilistic method” by N. Alon and J. Spencer).  Fix a set of three colors and independently color each vertex of $G$ into one of them. Given an edge, a probability that it is non-monochromatic is $\frac 23$. Thus the expectation of the number of non-monochromatic edges is $\frac 23e(G)$, hence there is so many non-monochromatic edges in at least one of the colorings. Let $H$ be a graph with $V(H)=V(G)$ and these edges. 
A: Here's a non-probabilistic proof. Given two sets $A,B$ of vertices, let $e(A,B)$ be the number of edges with one endpoint in $A$ and one in $B$. Split the vertices into three sets $V_1,V_2$ and $V_3$ in such a way that the sum
$$e(V_1,V_2)+e(V_1,V_3)+e(V_2,V_3)$$
is as large as possible. We claim that $e(V_1,V_2)+e(V_1,V_3)+e(V_2,V_3) \geq \frac{2}{3}e(G)$, which will be enough to solve the problem because we can make a tripartite graph by deleting the edges inside of $V_1$, the edges inside $V_2$ and the edges inside $V_3$. 
The trick is to show that, for every $v\in V_1$, the number of neighbours of $v$ in $V_2$ plus the number of neighbours of $v$ in $V_3$ is at least twice as large as the number of neighbours of $v$ in $V_1$. If not, then for some $i\in \{2,3\}$, we must have that $v$ has more neighbours in $V_1$ than in $V_i$ and we can remove $v$ from $V_1$ and put it in $V_i$ instead, and this will give us a new partition $V_1',V_2'$ and $V_3'$ such that
$$e(V_1',V_2')+e(V_1',V_3')+e(V_2',V_3')>e(V_1,V_2)+e(V_1,V_3)+e(V_2,V_3)$$
but this contradicts the choice of the original partition. 
Now, by symmetry, every vertex has at least twice as many neighbours in the other two classes than it has in its own. Thus, the number of edges going between $V_1,V_2$ and $V_3$ is at least
$$\frac{1}{2} \sum_{v\in V(G)}\frac{2}{3} d(v) = \frac{2}{3}e(G).$$
