Consider the following language and prove that Clique is dec

Consider the following language and prove that Clique is decidable.?

Only serious answers please. I really need this one.

Consider the language Clique = {(G, k)| G = (V, E) is an undirected graph, k > 0 is\' a natural number, and there exist k distinct vertices v_1, ..., v_k so that (v_i, V_j) epsilon E for each 1 lessthanorequalto inotequalto j lessthanorequalto k Prove that Clique is decidable.

Solution

From the definition of CLIQUE provided in the question, it can be said that CLIQUE is simply a sub-graph with k vertices and every two vertices represented as v_i and v_j are connected.

Consider graph G and the following algorithm:

We can repeat this procedure for k = 1 to n where n is the total number of vertices in graph G.

Since, the procedure is followed non-deterministically, therefore, all possible sub-graphs are checked. This means it is a polynomial time algorithm.

Since there exists a polynomial time algorithm which can determine whether CLIQUE exists or not. Therefore, this problem is decidable.