[proofplan]
We compute $\omega(G)$ by querying the decision oracle on the same graph $G$ with all possible clique-size thresholds. The key observation is that the oracle answer is yes exactly for thresholds $k$ satisfying $k \leq \omega(G)$, so the largest yes threshold is the clique number. Since there are only $|V|$ possible positive thresholds and each query has polynomial size in the encoding of $G$, the oracle algorithm runs in polynomial time.
[/proofplan]
[step:Define the oracle algorithm by scanning all clique thresholds]
Let $G=(V,E)$ be a finite undirected graph, and let $n := |V|$. Define an oracle algorithm $A^{\mathrm{CLIQUE}}$ as follows.
If $n=0$, the algorithm returns $0$. If $n \geq 1$, the algorithm initializes an integer variable $m := 0$. For each integer $k \in \{1,\dots,n\}$, it queries the oracle $\mathrm{CLIQUE}$ on the instance $(G,k)$. If the oracle answers yes, the algorithm replaces $m$ by $k$; if the oracle answers no, it leaves $m$ unchanged. After all $n$ queries have been made, the algorithm returns $m$.
[/step]
[step:Show that the largest yes threshold is exactly $\omega(G)$]
We prove that the value returned by $A^{\mathrm{CLIQUE}}$ is $\omega(G)$.
If $n=0$, then $V=\varnothing$, so $G$ has no nonempty clique and $\omega(G)=0$. The algorithm returns $0$, as required.
Assume now that $n \geq 1$. For each $k \in \{1,\dots,n\}$, the oracle answers yes on $(G,k)$ if and only if $G$ contains a clique of cardinality at least $k$. By the definition of the clique number, this is equivalent to $k \leq \omega(G)$. Therefore the set of thresholds receiving a yes answer is precisely
\begin{align*}
\{k \in \{1,\dots,n\} : k \leq \omega(G)\}.
\end{align*}
Since every clique in $G$ is a subset of $V$, one has $0 \leq \omega(G) \leq n$. Hence, when $n \geq 1$, the largest integer threshold in $\{1,\dots,n\}$ receiving a yes answer is $\omega(G)$ if $\omega(G)\geq 1$, and no threshold receives a yes answer if $\omega(G)=0$. In both cases the variable $m$ after the scan is exactly $\omega(G)$.
[guided]
The oracle does not directly output the maximum clique size. It only answers threshold questions: for a given integer $k$, does $G$ have a clique of size at least $k$? The reason the scan works is that these threshold answers encode the maximum.
First consider the empty graph case. If $n=|V|=0$, then $V=\varnothing$, so the only subset of vertices is empty. Thus there is no clique of positive cardinality, and the clique number is $\omega(G)=0$. The algorithm returns $0$, so the result is correct in this case.
Now assume $n \geq 1$. Fix a threshold $k \in \{1,\dots,n\}$. By the definition of the decision problem $\mathrm{CLIQUE}$, the oracle answers yes on $(G,k)$ exactly when there exists a clique $C \subseteq V$ with $|C| \geq k$. By the definition of $\omega(G)$ as the maximum cardinality of a clique in $G$, such a clique exists exactly when $k \leq \omega(G)$. Therefore the yes thresholds are exactly
\begin{align*}
\{k \in \{1,\dots,n\} : k \leq \omega(G)\}.
\end{align*}
This set has largest element $\omega(G)$ whenever $\omega(G)\geq 1$. If $\omega(G)=0$, then the set is empty, and the algorithm keeps its initialized value $m=0$. Thus, whether or not $G$ has a nonempty clique, the final value of $m$ is precisely $\omega(G)$.
[/guided]
[/step]
[step:Verify that the oracle computation uses polynomial time and polynomial-size queries]
The algorithm makes at most $n=|V|$ oracle queries. Each query has the form $(G,k)$ with $1 \leq k \leq n$, so its encoding consists of the encoding of $G$ together with an integer bounded by $n$. Thus every query has size polynomial in the input size of $G$.
Outside the oracle calls, the algorithm performs a linear scan over $\{1,\dots,n\}$ and updates one integer variable. This takes time polynomial in the input size of $G$. Therefore $A^{\mathrm{CLIQUE}}$ is a deterministic polynomial-time oracle algorithm computing $\omega(G)$ from oracle access to $\mathrm{CLIQUE}$.
[/step]
