Simple graph has $n$ vertices and the degree of every vertex is at most $4$. Prove that we can split the vertices to three groups such that the number of edges with vertices in the same group does not exceed $n/2$.
I've tried with a simple induction, but induction step is giving me a headache. It seems that taking an arbitrary vertex out of the set with $n+1$ vertices is not a good idea... Also, since every vertex in complementary graph $G'$ has a degree at least $n-5$ we have by handshake lemma at least $$n(n-5)\over 2$$ edges, so by Turan theorem we have in $G'$ at least $n+5\over 5$ clique, so in the graph $G$ we have an independatnt subgraph with at least $n+5\over 5$ vertices. But I'm not sure if this is of any help.