# 3 coloring of vertices in a graph

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?

-
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

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.

-
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