1. Let G = (V;E) be an undirected graph with n nodes. Recall that a subset of the nodes is called a clique if every two of them are joined by an edge. (a) Consider the following Largest Degree First1 greedy algorithm: Sort the nodes in order of decreasing degree. v largest degree node in G = (V;E) C {v}, remove v from V while not empty V do for each node u > V (largest degree to smallest) do if u is connected to every node in C then C C 8 {u} Remove u from V return C Give an example where the rst node selected by the greedy algorithm is part of a clique with maximum size, but the greedy algorithm does not return a maximum- sized clique. (b) Give an algorithm (not necessarily polynomial time) that, given an unweighted undirected graph, nds a clique of size k if one exists in the graph. i. State your algorithm ii. What is the running time of your algorithm? iii. Suppose it takes a minute to run your algorithm on a graph of 10 nodes with k = 5. What, roughly, is the number of the nodes n in the largest graph on which you will be able to run your algorithm with k = n 2 in about 3 days (72 hours)? That is, is it 20? 50? Hundreds of nodes? Thousands? Tens of thousands? Justify. (c) Give a polynomial time algorithm that, given an unweighted undirected graph G = (V;E) and a subset of nodes C b V , checks whether C is a clique of size k in G. What is the running time of your algorithm? 1Recall that the degree of a node is the number of edges incident on that node, that is the number of edges of which that node is a part