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.

  • $\begingroup$ How do you know such a locally best partion exists? $\endgroup$ – Aqua Oct 24 '19 at 19:56
  • 1
    $\begingroup$ By starting at an arbitrary partition and improving it until we can't. I've edited my answer. $\endgroup$ – 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.

  • $\begingroup$ 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$. $\endgroup$ – Misha Lavrov Oct 24 '19 at 0:51
  • $\begingroup$ Yes, that was required. $\endgroup$ – Aqua Oct 24 '19 at 9:13

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.