Induction Proof on Independent Set Variation Algorithm So I am given this blackbox algorithm, in which given a Graph G and a integer k, it returns yes if there is an independent set of size k, no otherwise.

My algorithm is suppose to output impossible if there is no independent set of size k, or output an independent set of size k if it exists.

How might this be approached?
Let $G$ be a graph with an independent set of size $k$, and let $v$ be an arbitrary vertex. There are two potential types of independent sets of size $k$ in $G$:


Independent sets not containing $v$: These are independent sets of size $k$ in $G \setminus \{v\}$.
Independent sets containing $v$: These are formed by adding $v$ to independent sets of size $k-1$ in $G \setminus \{v\} \setminus N(v)$, where $N(v)$ is the neighborhood of $v$.


Using an oracle for independent set, we can find which of these cases happen.

The basic idea can be implemented in many ways. Here is a recursive implementation, which uses the oracle $O(G,k)$, which answers whether $G$ contains an independent set of size $k$.


Procedure $I(G,k)$
Input: Graph $G$ and integer $k \geq 1$ 
Output: Independent set of size $k$ in $G$, or "No" if none exists


If $O(G,k)$ returns "No", then return "No".
Let $v \in G$ be arbitrary.
If $k = 1$, return $\{v\}$. Otherwise, continue.
If $O(G \setminus \{v\},k)$ returns "Yes", return $I(G \setminus \{v\},k)$.
Otherwise, return $O(G \setminus \{v\} \setminus N(v),k-1) \cup \{k\}$.