4. In an undirected graph, a triangle consists of three vertices having an edge between every pair. A 3-labelling is an assignment of one of three colors to each vertex. (Adjacent vertices do not necessarily need to have different colors.) Given a 3-labelling of an undirected graph, a triangle is tri-chromatic if its three vertices are assigned three different colors. (a) Describe and analyze an efficient randomized algorithm that, given an undirected graph as input, outputs a 3-labelling that in expectation has at least ths of the maximum possible number of tri-chromatic triangles. (b) Between Markov's Inequality and Chernoff bound, determine which tool is better for finding an upper bound on the probability that the algorithm in part (a) will find more than half of the possible number of tri-chromatic triangles. 4. In an undirected graph, a triangle consists of three vertices having an edge between every pair. A 3-labelling is an assignment of one of three colors to each vertex. (Adjacent vertices do not necessarily need to have different colors.) Given a 3-labelling of an undirected graph, a triangle is tri-chromatic if its three vertices are assigned three different colors. (a) Describe and analyze an efficient randomized algorithm that, given an undirected graph as input, outputs a 3-labelling that in expectation has at least ths of the maximum possible number of tri-chromatic triangles. (b) Between Markov's Inequality and Chernoff bound, determine which tool is better for finding an upper bound on the probability that the algorithm in part (a) will find more than half of the possible number of tri-chromatic triangles