Suppose you are given a polynomial-time algorithm for the following problem related to INDEPENDENT SET:
INDEPENDENT SET VALUE
Input: An undirected graph $G$.
Output:The size of the largest independent set in G (but not the set itself).
Show how you can use this algorithm to solve the INDEPENDENT SET problem in polynomial time: given a graph $G$, return an independent set which is as large as possible.
Any help would be really appreciated. I am pretty lost in this question
Hint: Suppose you run INDEPENDENT SET VALUE on $G$ and get $n$. Then you delete a vertex from $G$ to get $G'$ and run INDEPENDENT SET VALUE on $G'$. What are the possible results? What might you learn from each of the possible results?