Finding maximal cardinal independent set given oracle

Question

The problem is given an oracle $O(G, k)$ that would say if graph G contains IS of size k devise an algorithm for finding independent set of max cardinality that makes poly number of calls to the oracle. My attempt has been that first finding the maximal possible size and then try to find the set of that size by removing vertices one at a time. I understand for a given node it either has to be in or not in the set, then I noticed that that there are multiple overlaps between chain of removals and I could devise a DP algorithm of sorts. But I'm just really stuck after that and was wondering if any hint could be given.

Answer 1

Let $O(G)$ be an oracle that returns the maximum cardinality of an independent set in $G$; you can implement it given your oracle using binary search.

Pick an arbitrary vertex $v$, and form a graph $G'$ by removing $v$ and all its neighbors. If $O(G') < O(G) - 1$ is false, then $v$ doesn't participate in a maximum cardinality independent set, and we try more vertices until we find a vertex that does. If $O(G') = O(G) - 1$, then we put $v$ aside, and continue in the same way with $G'$.

Taking all vertices put aside, we obtain a maximum cardinality independent set of $G$.