I am trying to understand the following algorithm for Self reducibility of Clique.Here we have a MBClique black box algorithm, which return yes/no for parameters  where G is a graph and K is a natural number. It answers the question: Does G has a clique of K size? - Our aim is then to use this Decision algorithm to search what the actual Clique graph is.Given this Graph below, we can see it has a clique of size 3.The search algorithm is as follows (it was extracted from the CSE 200: Computability and Complexity @ UCSD lecture notes, page 4):Ok, so now given an algorithm MBClique that returns yes/no we are trying to search the actual k-clique. Suppose the graph of the image above is sent as parameter and k=3.In the first if it passes through.In the immediate after For loop all edges that don't affect the size of the clique are removed.Now my question: what is the Repeat...Until part of the algorithm for? In my understanding after the For loop I already have the respective Graph that I want as an answer.Thanks.
Self-reducibility of Clique
algorithms;search algorithms
The Repeat loop is not strictly necessary.  The algorithm would still be correct without it.  In fact, the Repeat loop actually has no effect, though proving this takes a little bit of work.If the graph $G$ has no $K$-clique, then this procedure correctly halts.  So assume the graph $G$ has at least one $K$-clique.  The interesting case is where it has multiple $K$-cliques.Associate each $K$-clique with a vector $(x_1,x_2,\dots,x_K)$ representing the vertices of the clique, in increasing order.  Now order these cliques by lexicographic order on the vectors.  Let's focus on the $K$-clique whose corresponding vector is lexicographically largest; call this the golden $K$-clique.  It is possible to prove that For loop removes everything but the golden $K$-clique: when the For loop terminates, all that remains is a subgraph containing exactly $K$ vertices, namely, the golden $K$-clique.  Therefore, the Repeat loop does nothing.In other words, you can remove the Repeat loop, and this procedure will always produce the same output.  (In particular, you were worired that the Repeat loop might remove a vertex from an actual clique -- but the above reasoning shows that this can never happen.)So, the Repeat loop is unnecessary.  Why is it there?  Maybe to make the proof of correctness for this algorithm a bit easier.  But if you find the algorithm easier to understand if you omit the Repeat loop, go ahead and pretend it's been removed -- that will work, too.