# How many triangles may a connected simple graph with m edges have at most?

Suppose a connected simple graph has m edges and there are at most n vertices and the degree of each vertex is at least k. How many triangles are there in the graph at most? The tighter the bound, the better.

A simple graph can have at most $\binom{n}{2}$ edges, which would make it complete. The spectrum of $K_{n}$ is $(n-1)$, with multiplicity $1$; and $-1$, with multiplicity $n-1$. So $K_{5}$ has eigenvalues $4, -1, -1, -1, -1$. Now the number of triangles in a complete graph is given by $\sum_{i=1}^{n} \lambda_{i}^{3} = (n-1)^{3} - (n-1)$, for $\lambda_{i}$ an eigenvalue of $K_{n}$ (on the adjacency matrix). Each edge you remove from $K_{n}$ removes at most $n-2$ triangles.