Fix $n>4$. Is there a characterization of the set $T\_n$ of all natural numbers $t$ such that there is some graph on $n$ vertices with exactly $t$ distinct triangles? For example, it's clear that {$1,2,\ldots,n$} $\subseteq T\_n$ and $\binom{n}{3}-1 \notin T\_n$; what else can we say?



Is it possible to have t triangles in some graph on n vertices?
I will argue that the following are true: 


* For any $\epsilon \gt 0$ and all large enough $n$, $T\_n$ contains all integers less than $\binom{n}{3}-\epsilon n^2.$
* For any fixed positive integer $c$ there is a finite list of expressions which accounts for all numbers larger than $\binom{n}{3}-cn-n/2$ provided that $n$ is large enough.


For $n \gt 14$ the largest members of $T\_n$ are precisely 


* $\binom{n}{3}$ then
* $\binom{n}{3}-n+2$ then
* $\binom{n}{3}-2n+r $ for $r=4,5$ then
* $\binom{n}{3}-3n+r $ for $r=6,7,8,9$ then
* $\binom{n}{3}-4n+r $ for $r=8,9,10,11,12,14$


A simple construction and simple bounds are enough to show that $T\_n$ contains all integers less than $\binom{n}{3}-n^2.$ The same simple construction with more sophisticated bounds evidently shows that for any $\epsilon \gt 0$ and all large enough $n$, $T\_n$ contains all integers less than $\binom{n}{3}-\epsilon n^2.$ 


First a side result. Every integer can be expressed as a sum of three triangular numbers. I asked [elsewhere](https://mathoverflow.net/questions/108075/sum-of-three-bounded-triangular-numbers) : What is the smallest positive integer $s=s\_m$ which can **not** be written in the form $$s=\binom{a}{2}+\binom{b}{2}+\binom{c}{2}$$ subject to $\max(a,b,c) \le m?$ For now I will say that obviously, for all $m $, $s\_m \ge \binom{m+1}{2} .$


Consider this simple construction: Start with $K\_{n-3}$ which already has $\binom{n-3}{3}$ triangles. Adjoin three further vertices $u,v,w$ with no edges between them but allow each to be connected to all, some or none of the other $n-3$ vertices. This will allow all triangle counts of the form $\binom{n-3}{3}+\binom{a}{2}+\binom{b}{2}+\binom{c}{2}$ subject to $\max(a,b,c) \le n-3$ and hence at least everything from $\binom{n-3}{3}$ up to $\binom{n-3}{3}+\binom{n-2}{2}-1=\binom{n}{3}-(n^2-5n+8).$ We may assume by inductive hypothesis and a few very small examples that using $n-1$ or less vertices we can get all counts up to $\binom{n-1}{3}-((n-1)^2-5(n-1)+8)=\binom{n-3}{3}+n-5.$ Hence we can get all counts from $0$ up to $\binom{n}{3}-(n^2-5n+8)$ using this construction.




---


If I understand a rather impressive answer (in a comment) to my question, for any $\epsilon \gt 0$, $s\_m \ge (3/2-\epsilon)m^2$ for all large enough $m.$ Hence for large enough $n$ we can get all counts up to $\binom{n-3}{3}+(3/2-\epsilon)(n-3)^2=\binom{n}{3}-(\epsilon n^2+O(n)).$




---


Consider now the largest counts in $T\_n.$ They must result from removing only a few edges from $K\_n$. Suppose that $c$ edges are removed and let $H$ be the graph formed by the removed edges. If $H$ is $c$ disjoint edges, this kills $c(n-2)$ triangles. In general the number of killed triangles is $c(n-2)-p-2t$ where $t$ is the number of triangles in H (since these triples get counted three times by $c(n-2)$) and $p$ is the number of paths of length two in $H$ which are not part of a triangle in $H.$ To find the exact spectrum of values requires not an enumeration but simply a classification of which triples $c,p,t$ represent possible values for the edge,path and triangle count of graph. Hence all triangle free graphs with $v$ vertices, $c$ edges and degree sequence $d\_1,d\_2,\cdots,d\_v$ give (when removed) the same count: $\binom{n}{3}-\sum\_1^v\binom{d\_i}{2}.$ We need not know how many ways a certain degree sequence can be obtained, only if it can be realized in at least one one.


