Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

How can we prove that there exists a coloring of vertices for graph $G$ such that at least 2/9 fraction of all triangles in $G$ whose vertices have different colors?

share|cite|improve this question
I would consider rephrasing your command into a question, as you are asking the other users a favor, not giving us an assignment. – Arthur Oct 9 '12 at 12:26
Sorry, just did that, hope it is what you mean. – LittleSweet Oct 9 '12 at 12:29
up vote 1 down vote accepted

Color the graph randomly, the probability that a triangle whose vertices have different colors is $\frac{3 \times 2}{3 \times 3 \times 3}=\frac{2}{9}$. Let $X_{t}$ be the indicator random variable that $t$ has distinct colors, then $E[X_{t}]=\frac{2}{9}$. Let $T$ be the set of all triangles and $X=\sum_{t \in T}X_{t}$, by linearity of expectation, the expected number of triangles is $E[X]=\sum_{t \in T}E[X_{t}]=\frac{2}{9}|T|$. By probabilistic method, there exists a coloring that at least $\frac{2}{9}$ of triangles receive 3 distinct colors.

share|cite|improve this answer
That's a step forward, but your proof is incomplete. (Note: the events "triangle X is assigned 3 distinct colours" and "triangle Y is assigned 3 distinct colours" might not be independent.) – Douglas S. Stones Oct 9 '12 at 12:39
You are right. Do you know how to continue? – LittleSweet Oct 9 '12 at 12:50
Find the expected proportion of triangles that have 3 distinct colours. Then use the probabilistic method. – Douglas S. Stones Oct 9 '12 at 12:54
Thanks, I have modified the proof. – LittleSweet Oct 9 '12 at 16:04
Another step forward, but still not finished. You've shown that the average number of triangles that receive 3 distinct colours is 2/9. You now need to show that this implies there exists a colouring in which the proportion of triangles that receive 3 distinct colours is 2/9. This is where you use the magic of the probabilistic method! (PS. If I were marking this, I would take off marks for not citing the use of "linearity of expectation".) – Douglas S. Stones Oct 9 '12 at 21:23

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

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