Time Complexity of k-clique problem with fixed k
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.