Number of edges required to guarantee $K_3$ as subgraph I am trying to solve a given problem: Find an algorithm to determine if a graph has a clique of size 3 in $O(n^{2.81})$ steps. The hint given is that $2.81 &gt; \log 7$. In order to solve this I came up with a conjecture: if $m &gt; n^{\log 7}$ then the graph has $K_3$ as a subgraph. This will easily solve the problem if the conjecture is true. 

I am trying to argue by contradiction: Let $m &gt; n^{\log 7}$ and assume there does not exist a $K_3$ subgraph. Then for any set of three vertices there are exactly 7 choices for how to connect them. However, I am stuck as to how to progress from here.

Does anyone see a way to prove this, or if the conjecture is even true. I'm also interested to see if the conjecture can be extended, i.e. if $m &gt; n^{\log 2^k -1})$ does there exist a $K_k$ subgraph?
Hint: Matrix multiplication runs in time $O(n^{2.71})$. A relevant matrix is the adjacency matrix of the graph.

Actually, this has been improved several times in the past very. Recently, Le Gall improved this to time $O(n^{2.3728639})$. It is conjectured that matrix multiplication runs in time $O(n^{2+\epsilon})$ for every $\epsilon &gt; 0$.