Your friend likes getting together small groups of extremely independent people. He claims to have written a super-fast solver for the following graph problem to help him perform this: He mapped all people he ever considered inviting as an undirected graph G = (V, E) with the set of nodes representing people, and two nodes v, w V connected by an edge if they regularly talk. He views two people v, w V as very independent if not only they are not connected by an edge, but also they have no shared neighbor u, that is, no node u with edges (u,v) and (u,w) in E (the reason is that such a u may be influencing both v and w, which does make the two of them less independent). When he is arranging a meeting, he identifies a subset S V of potential candidates, and then looks for k people in S that are very independent. So the VeryIndependent Set problem is given an undirected graph G = (V,E), a subset of nodes S V , and an integer k decide if there is a very independent set I S of size k.

You are impressed by what your friend's code can do, and wonder if this code is useful to solve the famous Independent Set Problem also. Show that given an undirected graph G and integer k for the Independent Set problem, you can solve this problem by a single call your friend's code. It is okay to modify G to a new graph G before calling your friend's code as long as G is polynomial in the size of G. In providing a solution to this problem you need to do the following:

• provide a polynomial time algorithm that converts an input to the Independent Set problem, an undirected graph G = (V,E) and an integer k to an input to the VeryIndependent Set problem, which consists of a graph G = (V , E), S V and integer k
• prove that if G = (V, E) has an independent set of size k then G has a very independent subset of the set S of size k
• and prove that if G = (V,E) has no independent set of size k then G also doesn't have a very independent subset of the set S of size k