Find a Cook Reduction from $R_{Clique}$ to its determinist problem
Your algorithm doesn't return a $k$-clique. Simply consider a connected graph $G$ that is a proper supergraph of a $k$-clique, and an isolated vertex $x$. Your algorithm with input $G+x$ returns $G$.
You can solve your problem as follows:

While $\exists $ a vertex $v$ of $G$ such that $B(G-v)$ returns true:

Delete $v$ from $G$


Return $G$.

Let $G^* = (V^*, E^*)$ be the graph returned by the algorithm.
Since the algorithm preserves the invariant &quot;G contains a $k$-clique&quot;, $G^*$ must also contain a $k$-clique. This means that we only need to prove that $G^*$ is not a supergraph of a $k$-clique.
Suppose towards a contradiction that there exists a proper subset $C$ of $V^*$ such that $|C|=k$ and the subgraph of $G^*$ induced by $C$ is a $k$-clique. Then, for any vertex in $v \in V^* \setminus C \neq \emptyset$,  $G-v$ also contains a $k$-clique. This shows that the algorithm cannot return $G^*$ and yields the sought contradiction.