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