Es sei ein Graph ´G = (V, E)´ gegeben. Es sei ein polynomialer Algorithmus für das Cliquenproblem gegeben. Es wird nun der Reihe nach getestet, ob es eine Clique aus ´#(V)´, ´#(V) − 1´, ´#(V) − 2´, usw. Elementen gibt, und bei einer positiven Antwort gestoppt. Erfolgt dies bei ´r´, so ist ´r´ die maximale Größe einer Clique in ´G´. Da spätestens bei ´2´ (wenn es eine Kante gibt) bzw. ´1´ (wenn ´E = O/´) getstoppt wird, und demzufolge weniger als ´#(V)´-mal ein polynomialer Algorithmus ausgeführt wird, ist dieser Algorithmus zur Bestimmung der maximalen Cliquengröße auch polynomial. Gibt es umgekehrt einen polynomialen Algorithmus zur Bestimmung der maximalen Cliquengröße ´r´, so gibt es genau dann eine Clique der Größe ´k´ (aus dem Cliquenproblem), wenn ´k <= r´ gilt. Daher ist dann auch das Cliquenproblem in polynomialer Zeit entscheidbar.