It is known that a simple graph with $n$ vertices and $m$ edges has at least $\frac{m}{3n}(4m - n^2)$ triangles. Some proofs can be found here.
Here I repeat what I have understood (hopefully correctly) from the above link: let $G=(V,E)$ be the graph, and $d(v)$ be the degree of vertex $v \in V$, then given an edge $\{v_1,v_2\} \in E$ from it we can get at least $d(v_1)-1+d(v_2)-1-(n-2)$ triangles. This is because $d(v_1)-1$ counts all edges outgoing from $v_1$, excluding $\{v_1,v_2\}$, and similarly for $d(v_2)-1$. Also, there are $n-2$ vertices different from $v_1,v_2$ and we can build a triangle with $\{v_1,v_2\}$ if there is an edge from $v_1$ and another edge from $v_2$ to one of these vertices. By the pidgeonhole principle we get the minimum number of triangles subtracting $n-2$.
Now let $t_3(n,m)$ the number of triangles in the graph, we have:
$$t_3(n,m) \ge \frac{\sum_{\{v_1,v_2\}\in E}{\left( d(v_1)+d(v_2)-n \right)}}{3} = \frac{\sum_{\{v_1,v_2\}\in E}{\left( d(v_1)+d(v_2)\right)}-nm}{3}$$
where we needed to divide by $3$ because the same triangle is counted for any of its three edges.
Note also that $\sum_{\{v_1,v_2\}\in E}{\left( d(v_1)+d(v_2) \right)} = \sum_{v \in V} d^2(v)$, and due to Titu's lemma, which is a direct consequence of Cauchy-Schwarz inequality, we have that $\sum_{v \in V} d^2(v) \ge \left(\sum_{v \in V} d(v)\right)^2/n=(2m)^2/n$. Putting that all together we finally have:
$$t_3(n,m) \ge \frac{m}{3n}(4m - n^2)$$
For example, if $G$ is a triangle, then $n=3$, $m=3$ and $t_3(3,3) \ge 1$, which is consistent with the actual number of triangles, i.e. $1$.
Now I want to generalize the inequality: say that $m$ is the number of $K_r$ complete subgraphs in $G$ and $t_{r+1}(n,m)$ the number of $K_{r+1}$ complete subgraphs it has.
Let $E_r$ be the set formed by all sets of vertices of each $K_r$ subgraph in $G$, i.e. if the vertices of a $K_r$ are $v_1, \ldots, v_r$ then $\{v_1, \ldots, v_r\} \in E_r$. Let $d_r(v)$ the number of $K_r$ subgraphs with a vertex $v \in V$.
Reasoning like for the case $r=2$ I think we can write:
$$t_{r+1}(n,m) \ge \frac{\sum_{\{v_1,\ldots,v_r\}\in E_r}{\left( d_r(v_1)+\ldots +d_r(v_r)-r-(n-r)(r-1) \right)}}{r+1}$$
Again $-r$ in the numerator is for excluding from the $d_r(v_i)$ the $K_r$ graph with vertices $v_1, \ldots, v_r$, $n-r$ are the remaining vertices, again we apply the pidgeonhole principle, but in this case we must multiply by $r-1$ (I am very dubious about this point). And finally we must divide everything by $r+1$ because we counted the $K_{r+1}$ subgraph $r+1$ times, one time for each of its composing $K_r$.
We have again $\sum_{\{v_1,\ldots,v_r\}\in E_r}{\left( d_r(v_1)+\ldots +d_r(v_r) \right)} = \sum_{v \in V} d_r^2(v)$, and again due to Titu's lemma, we have that $\sum_{v \in V} d_r^2(v) \ge \left(\sum_{v \in V} d_r(v)\right)^2/n=(rm)^2/n$. Finally:
$$t_{r+1}(n,m) \ge \frac{m}{(r+1)n}(r^2m-nr-n(n-r)(r-1))$$
For example for $r=3$ we have:
$$t_4(n,m) \ge \frac{m}{4n}(9m+3n-2n^2)$$
Let $G = K_4$, then $n = 4$, $m = 4$ and $t_4(4,4) \ge 4$, but actually we have just one $K_4$.
What I am doing wrong? I suspect that the problem is where I said I am dubious (the $(n-r)(r-1)$). Someone can help?
