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 ...

Question

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.

Answer 1

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.

Answer 2

By handshake lemma we have in $G$ at most $2n$ edges. By this "theorem" every graph $G$ has a bipartite subgraph with at least half of the edges of $G$ we have two parts $A$ and $B$ with at most $n$ edges in both, so if $a,b$ are the number of edges in each we have $a+b\leq n$ so one of them say $A$ has at most $ n/2$ edges. Now again by the same theorem we can divide $B$ in two parts $X$ and $Y$ with $x,y$ edges each and $x+y\leq b/2\leq n/2$ and thus we are done.