Find a Cook Reduction from $R_{Clique}$ to its determinist problem The question is to find Find a Cook Reduction from $R_{k-Clique}$ to its determinist problem.
Basically:
k-Clique: a group of $k$ nodes in the graph such there is an edge between every two nodes.
Suppose you are allowed to use an algorithm (B) that in $O(1)$, given as input a graph $G$ and a number $k$, returns whether the graph includes a $k-Clique$ or not.
Use B to define an algorithm (A), that in polynomial time, given as input a graph $G$ and a number $k$, returns a $k-Clique$ if it exists, and a symbol if it doesn't.
My idea:
My idea was to define something as follow:
1. While the size of the graph is greater than k
    2. Remove from the graph the node with the lowest deg
        1. check the new G with B, if yes, return it
        2. Else, continue

Something like that. I wasn't able to disprove it at least. But is it correct? How would I prove it?
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.