$k$-partite spanning subgraph I found an interesting problem:

Prove that for every $k>1$ any loopless undirected graph $G$ contains a $k$-partite spanning subgraph $H$ such that: $\left( 1-\frac{1}{k} \right)\deg_G(x) \le \deg_H(x)$ for any $x\in V(G)$.

But don't know how to start. Can anybody help?
 A: Let $H$ be a $k$-partite spanning subgraph of $G$ with the maximum number of edges among such subgraphs, with parts $X_1, \dotsc, X_k$.  Let $x \in V(G)$
and WLOG suppose $x \in X_1$.
Let $d = \deg_G(x) - \deg_H(x)$ be the number of edges "missing" at $x$.
We claim that $d \leq \frac{1}{k} \deg_G(x)$.
Suppose to the contrary that $d > \frac{1}{k} \deg_G(x)$;
equivalently, that $\deg_H(x) < \frac{k-1}{k} \deg_G(x)$.
All edges missing at $x$ were to other vertices in $X_1$.
All the edges from $x$ in $H$ are into some of the other $k-1$ parts $X_2, \dotsc, X_k$.
By the pigeonhole principle,
the number of edges $r$ from $x$ into some $X_i$ is at most $\frac{1}{k-1} \deg_H(x) <
\frac{1}{k-1} \frac{k-1}{k} \deg_G(x) = \frac{1}{k} \deg_G(x) < d$.
Consider the spanning subgraph $H'$ with $X_1' = X_1 \setminus \{x\}$
and $X_i' = X_i \cup \{x\}$.
If $H$ had $e(H)$ edges,
then $e(H') = e(H) + d - r > e(H)$,
contradicting that $H$ had the maximal number of edges.
This is a modification of example 1.4.2 in Theory and Application of Graphs by Junming Xu (generalizing from the bipartite case.)
