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.
Best Answer
Just pick a partition of $G$ into three parts that's "locally" the best: for each vertex $v$, moving $v$ to a different part wouldn't reduce the number of bad edges (that is, edges between vertices in the same part).
(To find such a partition, just start at any partition and, if it's not locally best, improve it: move a vertex to a different part. This reduces the number of bad edges, and we can't keep doing that forever.)
Since each vertex $v$ has degree at most $4$, there must be a part where $v$ has at most one neighbor. Since our partition must be a locally optimal one, it puts $v$ in such a part. So $v$ is incident to at most one bad edge.
Since this is true for all vertices, then there can be at most $n/2$ bad edges: for each of $n$ vertices, we count at most one bad edge, and each bad edge is counted twice. So we've found the partition we wanted.