k-partite Subgraph I'm just working on a problem, but can only show, that the statement is true for $k=2$.
Let $G$ be a graph with $E(G)$ edges and $k \ge 2$. Show, that there is a $k$-partite subgraph $G*$ of $G$, so that $E(G*) \ge \frac{k-1}{k}  E(G)$.
For $k = 2$, I solved the problem by induction over the number of vertices of $G$.
Thanks a lot
 A: I think induction works for any $k$.
Fix $k$, induct over the order $n$ of the graph.
If $k\leq n$, this is trivial, each vertex can be in its own partite set.
So assume it's true for all graphs of order $n$, and let $G$ be a graph of order $n+1$.
Pick a vertex $v$ of $G$. The graph $G-v$ has order $n$, so there's a $k$-partite subgraph $(G-v)^*$ of $G$ such that $|E((G-v)*)| \geq \frac{k-1}{k}|E(G-v)|$. We may assume without loss of generality that $(G-v)^*$ contains every vertex of $G-v$.
Let $V_1$, $V_2$, $\dots$, $V_k$ be the partite sets of $(G-v)^*$.
Choose the partite set $V_i$ that minimises $|N(v)\cap V_i|$ (so pick a partite set that contains the fewest neighbours of $v$), and notice that $|N(v)\cap V_i| \leq \frac{1}{k}|N(v)|$. Thus there are at least $\frac{k-1}{k}|N(v)|$ edges from $v$ to $G-V_i$.
The edges of $G$ that are not in $G-v$ are exactly those incident with $v$, so create $G^*$ from $(G-v)^*$ by adding $v$, and all the edges between $v$ and $(G-V_i)$.
$G^*$ is $k$-partite, since you can keep the same partite sets, and just put vertex $v$ into the partite set $V_i$.
