Any graph $G$ has a $k$-colorable subgraph?

Question

I'm trying to prove that, for each $k\in \mathbb{N}$ and each simple graph $G=(V,E)$, $G$ has a $k$-colorable subgraph $H=(V',E')$ such that $|E^\prime|\ge (1-1/k)|E|$. I think that i have to use probabilistic method. First step: randomly color ever vertex with one of $k$ colors, but how to continue? Any help would be greatly appreciated!