Professor Amongus has just designed an algorithm that can take as input any

undirected graph $G$ with $n$ vertices and a number $k$ and determine in $O(n^k)$ time

whether $G$ contains a clique of size $k.$ Does Professor Amongus deserve the Turing

Award for having just shown that $P=NP?$ Why or why not $?$

For answering the above question, we need to understand: What is a Clique $?$

A clique, $C,$ in an undirected graph $G=(V,E)$ is a subset of the vertices, CsubeV,

such that every two distinct vertices in the clique are adjacent. This is

equivalent to the condition that the $C$ is a subgraph of $G$ such that $C$ is a complete

graph.

Many versions of the Clique problem are NP$-$hard.

$k-$clique decision version is NP$-$complete.

k$-$clique problem:

Input: Undirected Graph $($V$,$ E$),$ and k

The output is a clique with $k$ vertices, if one exists, or an error value indicating it

doesn't exist.