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?


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

  • $\begingroup$ You need to colour the vertices independently in order to conclude that the probability for matching colours is $\frac1{k^2}$. $\endgroup$
    – joriki
    Dec 26, 2019 at 18:36
  • $\begingroup$ You are correct! each vertex has equal probability to be color in each color, regardless of the other vertices coloring choice. Meaning vertices where color independently. $\endgroup$ Dec 26, 2019 at 18:59
  • $\begingroup$ Thank you very much for your help! $\endgroup$
    – hydrogn84
    Dec 27, 2019 at 12:03
  • $\begingroup$ Could it be that one color has atmost $\frac{|E|}{k}$ edges but an another color has > $\frac{|E|}{k}$ edges ? $\endgroup$
    – Balaji sb
    Nov 20, 2022 at 3:02
  • 1
    $\begingroup$ @Balajisb The $\frac{|E|}{k}$ in this problem is a sum over all colors, not a separate quantity for each color. $\endgroup$ Nov 20, 2022 at 3:40

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .