We are given an undirected graph G = (V, E) and an integer k |V |. We want to compute a subset SV of size |S|k so as to maximize |E(S)|,where E(S)={(u,v)E:uS and vS} is the set of edges with both endpoints in S.

(a) Write down an LP-relaxation for this problem. (b) What is the smallest possible upper bound you can derive on the integrality gap of this LP relaxation?(it should be a function of n and k)