A simple graph $G$ has $k$-cliques but not $(k+1)$-cliques. Prove that there exists a $k$-partite $H$, and a bijection $f:V(G) \to V(H)$ so that $d_G(v) \leqslant d_H\big(f(v)\big)$.
In other words, $G$ itself may not be a k-partite, but by changing some of its edges we can obtain a k-partite $H$, so that the degree of each vertex is non-decreasing.
Example: $C_5$ has $K_2$ but not $K_3$, we can change (add and delete) the edges of $C_5$ to obtain $K_{2,3}$. By doing that, no vertex have decreased degree and we get a bipartite.