# Does the language defined in the details in NP-C or P?

It's known that: $$\textrm{CLIQUE} = \{(G,k): \mbox{G has a clique of size } k\}$$ is $$\textrm{NP-C}$$, but what if every vertex has 2 neighbours (as defined in $$\textrm{2d-CLIQUE}$$)? $$\textrm{2d-CLIQUE} = \{(G,k): \mbox{every vertex in G has exactly 2 neighbours and G has a clique of size } k\}.$$

Assuming that every vertex of $$G$$ has degree $$2$$, no clique of $$G$$ can have more than $$3$$ vertices. Then $$\textrm{2d-CLIQUE}$$ is trivially in $$\textrm{P}$$ and, if $$\textrm{P} \neq \textrm{NP}$$, it cannot be $$\textrm{NP}$$-complete.
Under the above assumption (which is trivial to check), $$(G,k) \in \textrm{2d-CLIQUE}$$ iff one of the following conditions holds:
• $$k=0$$, or
• $$k \in \{1,2\}$$ and $$G$$ is not empty, or
• $$k = 3$$ and $$G$$ has a triangle, which can be checked in $$O(n)$$ time.
• For any constant $h \ge 0$, $h\textrm{d-CLIQUE}$ is in $\textrm{P}$. If $k>h+1$ there can be no $k$-clique. If $k \le h+1$ you can then enumerate all the $O(n^k) = O(n^{h+1}) = n^{O(1)}$ subsets of $k$ vertices of $V$ and check in $O(h^2)$ time each if they induce a clique. In fact this even works for $\textrm{CLIQUE}$ if $k = O(1)$. – Steven Mar 11 at 16:37