# Coming up with an adversary strategy for a clique of maximum size

I’m having trouble coming up with a good adversary strategy for this problem:

Input: a graph G

Output: the maximum size of any clique in G

Where the algorithm asks each time, “are vertices x and y adjacent?” and it could ask about any random pair of vertices in the graph.

So, I need an adversary strategy to force the algorithm to work for as long as possible. Here’s what I have so far:

• for any graph with n vertices, there exists n(n-1)/2 unique vertex pairs the algorithm can ask about
Following is a simple adversary strategy that makes the algorithm make $$\frac{n(n-1)}{2}$$ queries:
For every pair $$(x,y)$$, adversary answers "no", i.e., $$x$$ and $$y$$ are not adjacent.
Proof: Since the adversary is maintaining an empty graph, the answer is trivially a clique of size $$0$$. However, if the algorithm says "$$0$$" before making all $$\frac{n(n-1)}{2}$$ queries, then for any non-queried vertex pair $$(x,y)$$ the adversary can make $$x$$ and $$y$$ adjacent; hence forming a clique of size $$2$$, and thus proving the algorithm wrong.