The CLIQUE problem -- problem of finding the maximum clique in a graph -- is NP-complete. That is, CLIQUE is
- in NP and
- there is an NP complete problem, 3-SAT for one, that reduces to CLIQUE in polynomial time.
Part 2. above is fine -- all over in every resource and very well explained. For Part 1., from what I know, we need to have the following: Given a specific solution instance, we need to show that it can be verified, in polynomial time, that that solution is an answer to this problem. So for instance, given a specific graph and a subgraph of it, we should be able to check whether that subgraph is a clique of maximum size in that graph.
The resources I've read so far are phrasing this Part 1. here as "easy, straightforward, etc" or "it can be shown in $O(n^2)$ time that the given subgraph is a clique/not". However, the verification here is not just whether it's a clique, but also is whether it is a maximum clique in the graph. How can this be decided in polynomial time?
What am I missing here?