1. (Greedy Coloring Algorithm) The following psuedo-code that (allegedly) colors the vertices of a graph so that no two adjacent vertices receive the same color. Such a coloring is called a vertex-coloring of G. Algorithm GCA Input: A simple undirected graph G with vertices V (G) = { v1, v2;.....,vn}. (The list of colors to be drawn from will be {1, 2....., n}; GCA does not necessarily use all of these colors. Output: A vertex-coloring of G. For i = 1 to n do Li = {1,...... i} (Li is the list of colors that may be assigned to vi) For i = 1 to n do Set ci = the first color in Li (ci is the color assigned to vi) For each j with i < j and (vi, vj) E(G) do Set Lj := Lj \ ci Return each vertex, the color it was assigned, and the total number of colors used. (a) Prove that algorithm GCA is correct. (b) Show that the number of colors used by GCA on the vertices of G could be strictly greater than x(G) with an example and an explanation. (c) Under what general circumstances will the number of colors used by GCA be equal to x(G)? Illustrate your claim with an example and an explanation. Hint: the algorithm depends on the way the vertices are numbered to begin with. (d) What is the runtime of GCA (in terms of n)? (e) How can GCA be utilized to construct an algorithm to find the exact value of x(G) using part (c)? What is the runtime of your algorithm?