# Upper bound for monochromatic edges in vertex coloring with k colors

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?

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.

• You need to colour the vertices independently in order to conclude that the probability for matching colours is $\frac1{k^2}$. Dec 26, 2019 at 18:36
• 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. Dec 26, 2019 at 18:59
• Thank you very much for your help! Dec 27, 2019 at 12:03
• Could it be that one color has atmost $\frac{|E|}{k}$ edges but an another color has > $\frac{|E|}{k}$ edges ? Nov 20, 2022 at 3:02
• @Balajisb The $\frac{|E|}{k}$ in this problem is a sum over all colors, not a separate quantity for each color. Nov 20, 2022 at 3:40
The text passage discusses a mathematical problem related to graph theory, specifically about finding an upper bound for the number of monochromatic edges in a graph when vertices are colored with k colors. It includes a proof using the probabilistic method to show that the upper bound is \(\frac{|E|}{k}\).
single_question_with_answer
Given a text passage, determine:
    1. If it contains a mathematical question (including word problems or calculations)
    2. If an answer to that mathematical question is provided in the text

First, describe the content structure you found in 1-2 sentences.

Then provide your analysis in the following format:
TYPE: <one of the following values>
- NO_QUESTION
- SINGLE_QUESTION
- SINGLE_QUESTION_WITH_ANSWER
- MULTIPLE_QUESTIONS
- MULTIPLE_QUESTIONS_WITH_ANSWERS
system
# Upper bound for monochromatic edges in vertex coloring with k colors

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?

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.

• You need to colour the vertices independently in order to conclude that the probability for matching colours is $\frac1{k^2}$. Dec 26, 2019 at 18:36
• 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. Dec 26, 2019 at 18:59
• Thank you very much for your help! Dec 27, 2019 at 12:03
• Could it be that one color has atmost $\frac{|E|}{k}$ edges but an another color has > $\frac{|E|}{k}$ edges ? Nov 20, 2022 at 3:02
• @Balajisb The $\frac{|E|}{k}$ in this problem is a sum over all colors, not a separate quantity for each color. Nov 20, 2022 at 3:40
user
The text passage discusses a mathematical problem related to graph theory, specifically about finding an upper bound for the number of monochromatic edges in a graph when vertices are colored with k colors. It includes a proof using the probabilistic method to show that the upper bound is \(\frac{|E|}{k}\).

TYPE: SINGLE_QUESTION_WITH_ANSWER