Upper bound for monochromatic edges in vertex coloring with k colors

Question

I'm trying to find an upper bound of the number of monochromatic edges in a graph $G=(V,E)$, given k colors for Vertex coloring. An edge $e=(u,v)\in E$ is called monochromatic if both $u$ and $v$ have the same color.

If I understand right, for any $k > 0$, $G$ can be vertex k-colored so that at most $\frac {|E|}{k}$ of its edges are monochromatic. If it's true, how is it proved?

Answer 1

I'm assuming that by "vertex coloring" you are not referring to proper vertex coloring, since every proper vertex coloring has zero monochromatic edges.

I'll prove the claim using the Probabilistic method.

Given a graph $G=(V,E)$, and k colors, I'll define random coloring as a function $C:V\to[k]$ (where $[k]:=\{1,2....,k\}$) as follow: $$\forall v\in V, i\in[k]\ \ \ \ \mathbb {P}(c(v)=i)=\frac{1}{k}$$ Proposition $$\forall e\in E\ \ \ \mathbb {P}(e\text{ is monochromatic})=\frac{1}{k}$$ The proposition implies the expected number of monochromatic edges for such random coloring is $\frac{\vert E\vert}{k}$.

Therefore, at least one random coloring induce no more then $\frac{\vert E\vert}{k}$ monochromatic edges, otherwise, the expectation value would be higher.

The proposition proof is quite simple: $$\forall i\in [k],v,u\in V\ \ \ \ \mathbb P(c(u)=i\land c(v)=i) = \frac{1}{k^2}\implies\mathbb P(c(u)=c(v))=\frac{1}{k}$$ Where the last transition is true because there are k colors.