Show that for all integers $k \ge 2$ every graph $G$ contains a $k$-partite subgraph $H$ with $e(H) \ge \frac{k-1}{k}e(G)$.

Question

Show that for all integers $k \ge 2$ every graph $G$ contains a $k$-partite subgraph $H$ with $e(H) \ge \frac{k-1}{k}e(G)$.

Answer 1

See my answer to this question for $k=3$. The proof for an arbitrary $k$ is similar.