Time Complexity of k-clique problem with fixed k My question expands on a related question on the link, Why is the clique problem NP-complete? 
In that post the author argued that while the $k$-clique problem is NP-complete; for a fixed $k$ the $k$-clique problem is polynomial time solvable. The question "Prove that the presence of 3-clique in a graph can be decided in polynomial time" also appears in the book, S. K. Basu, "Design Method and Analysis of Algorithms, PHI, 2005, pg159.

To avoid any confusion, I felt it important to clarify that this would only be possible if the graph $G=(V,E)$ ($V$ is the set of vertices and $E$ is the set of edges) is fixed. In such a case a polynomial number of steps $R^m,$ (where $R=f(V,E)$, i.e. $R$ is a constant given by some function of vertices and edges) can be used to find the solution of 3-clique for example.  So the conclusion that finding 3-clique for a fixed graph has polynomial time complexity works perfectly fine until this point.

But such a polynomial time algorithm with time complexity less than or equal to linear time complexity can not be designed to find 3-clique, i.e. $m&gt;1$. Assuming that $k$ is fixed but $G$ is not fixed, in that case the complexity of finding 3-clique will then be exponential, unless someone can provide a polynomial time algorithm with complexity $R^m$, where $m\leq 1$ to find 3-clique for a fixed arbitrary graph. Since we are unable to prove that a polynomial time algorithm does not exist for 3-clique problem on an arbitrary graph, the computational complexity of the problem will hence be treated as being NP-complete based on the relationship $3SAT\leq_p k$-clique, a proof of which can be found in many standard books on algorithms.
A polynomial algorithm does exist for finding whether a graph contains a triangle. For one, you can go over all triplets $x,y,z$ of vertices, and check if the graph contains the triangle $\{x,y\},\{y,z\},\{x,z\}$. This algorithm takes $O(n^3)$. Surprisingly, there is a faster algorithm: take the adjacency matrix $A$ of the graph, and compute the trace of the matrix $A^3$. The graph contains a triangle iff the trace is positive. This algorithm takes $O(n^\omega)$, where $\omega &lt; 2.373$ is the exponent of matrix multiplication.