# 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 …

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.

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.

• How do you know such a locally best partion exists? – Aqua Oct 24 '19 at 19:56
• By starting at an arbitrary partition and improving it until we can't. I've edited my answer. – Misha Lavrov Oct 24 '19 at 20:15

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.

• I think this makes sure that within each of the resulting parts $A, X, Y$ there are at most $n/2$ edges. But it doesn't guarantee that the total number of edges inside $A$, $X$, and $Y$ is at most $n/2$. – Misha Lavrov Oct 24 '19 at 0:51
• Yes, that was required. – Aqua Oct 24 '19 at 9:13