# If P = NP, how do I prove I can find the maximum clique in polynomial time?

I want to prove that if P = NP, then there is a polynomial time algorithm for finding the largest clique in an undirected graph.

I understand how to use a verifier to find this but my issue is since P = NP it doesn't want me to use a verifier. I'm not sure how to approach this.

• basically its nearly by definition of NP completeness and that the problem is NP complete. – vzn Nov 21 '13 at 20:40

Assuming $P=NP$, then $CLIQUE \in P$, so you can test for a clique of size $k$ in polynomial time for all $k$. So you can just test for a clique of each size between $1$ and $n$ where $n$ is the number of nodes.