One can show, that a Graph with at least $n$ vertices and $m$ edges, has at least $\dfrac{4m}{3n}(m-\dfrac{n^2}{4})$. I was wondering, about the best lowest bound of this, and the best upper bound of this ( is the best upper bound truly, the number of triangles formed in the complete graph , i.e $ \Delta(G) \choose 3$ ?
[Math] Number of Triangles in a graph with $n$ vertices and $m$ edges
algebraic-graph-theorygraph theoryinequalitytriangles
Related Solutions
Circulant graphs can be used to realize the $\lfloor n\Delta/2 \rfloor$ bound in a large number of cases, and in the other cases, we can modify them slightly to achieve this bound.
- When $n$ is even and $\Delta$ is even (so $\Delta \leq n-2$), we pick a set of distances comprising $\Delta/2$ distances in $\{1,2,\ldots,n/2-1\}$.
For example, when $n=10$ and $\Delta=6$, we can take the distances $\{1,2,3\}$, which gives:
- When $n$ is even and $\Delta$ is odd, we pick a set of distances comprising $(\Delta-1)/2$ distances in $\{1,2,\ldots,n/2-1\}$ and $n/2$.
For example, when $n=10$ and $\Delta=5$, we can take the distances $\{1,2,5\}$, which gives:
- When $n$ is odd and $\Delta$ is even we pick a set of distances comprising $\Delta/2$ distances in $\{1,2,\ldots,(n-1)/2\}$.
For example, when $n=11$ and $\Delta=6$, we can take the distances $\{2,3,4\}$, which gives:
Finally, when $n$ is odd and $\Delta$ is odd (so $\Delta \leq n-2$), $n\Delta/2$ is not an integer, so we can't achieve the maximum with circulant graphs. The best we could possibly do is $\lfloor n\Delta/2 \rfloor$. To achieve this:
We take a $(\Delta-1)$-regular graph as above, but do not take distance $1$ edges (we need to take at most $(\Delta-1)/2 \leq (n-3)/2$ distances, so this is possible).
We observe that the edges of distance $1$ form a Hamilton cycle in the complement of the graph. We pick $(n-1)/2$ disjoint edges from this Hamilton cycle (i.e., no two edges share an endpoint), and add them to our construction.
For example, when $n=11$ and $\Delta=7$, we can take the above $6$-regular graph and add in edges around the outside as follows:
This gives $\lfloor n\Delta/2 \rfloor$ edges in every case (as expected).
Best Answer
An upper bound is $\frac 13{m \choose 2}=\frac {m(m-1)}6$ because at the most you can choose any two edges and have one triangle, then each triangle gets counted $3$ times.