Let be G=(V,E) un-directed graph. for coloring vertex of the graph we define "legal edge" which means the color of vertices in this edge are colored in different colors. Prove by probabilistic method that exists colored G in 3 colors which at least 2/3 of edges are legal.
I am able to prove it by induction method - but I don`t know how prove it formally by probabilistic method. if we raffle a graph, how can we say that the probability is bigger than 0?
Hint: if you colour the vertices at random from the $3$ colours (independently with equal probabilities)