For my first group: You were right!
There is a bug in my algorithm. To correct it, one has to remove also all the neighbors of v from the graph when we find that v is necessary for the IS (removing only v from the graph is not enough).
For my second group: Here is a description of the algorithm:
Assume that IS is in P. We show how we can find the largest IS in a graph G in a polynomial time. First we find the maximal k for which <G,k> in IS by |V| calls to the TM that decides IS in polynomial time. Let that k be k0. Next, we arbitrarily choose a vertex in G. We omit it from G and obtain a new graph G'. We check whether <G',k0> is in IS. If the answer is yes, we continue choosing vertices and omitting them, starting from G'. If the answer is no, we add the omitted vertex to our output list, and omit from G' all his neighbors as well, and then continue choosing vertices with the obtained graph and k0-1 instead of k0.