# Reduction from Maximum Independent Set to Independent Set Decision Problem

I was hoping someone would be able to help me with this question.

The Maximum Independent Set search problem is, given an undirected graph G, to output an independent set in G of maximum size.

Give a polynomial time algorithm for the Maximum Independent Set search problem which can use an oracle that solves instances of the Independent Set decision problem.

I can't see how you would do this without inputting every possible combination of the vertices into the Independent Set Problem, which obviously won't be polynomial time.

It is certainly possible to do so, as every $\mathcal{NP}-$complete problem is self-reducible.
Let us first remember the definition of decisional maximum independent set: given an undirected graph $G=(V,E)$ and $k \in \mathbb{N}$, does there exist $S \subseteq V$ with $|S| = k$ such that $\forall x, y \in S \ . \ (x, y) \notin E$ ?
Let $s$ be the size of the maximum independent set of $G$. We pick some $v \in V$ and we use our construction to determine the size of the maximum independent set of $G \setminus v$. That can be either $s$ or $s-1$. If it's $s$, then there exists a maximum independent set in $G$ that does not include $v$, therefore we can exclude $v$ from our search.