Induction Proof on Independent Set Variation Algorithm
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\}$.