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.


1 Answer 1


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.

Now that you have the max clique size, you just need to find it. You can do that by removing an abitrary node, then re-running then seeing if there still exists a clique of max size. You will be left with the max size clique.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.