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

Question

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\}. $$

Answer 1

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.