
DAVID FISHER, Department of Mathematics, University of Colorado at Denver, Denver, Colorado 802173364, USA 
The minimum number of triangles in a graph 
Given
, what is the minimum number of
triangles in a graph with n vertices and e edges? Let t_{n,e}be
the answer. For example, G has 7 vertices, 13 edges, and 3triangles.
=.12in
Since any graph with 7 vertices and 13 edges has at least 3triangles, we have t_{7,13}=3.
Trivially, t_{n,e}=0 if . McKay (1963) proved . Bollobás (1978) improved this by showing t_{n,e} is at least the piecewise linear function with nodes for . Fisher (1989) found a better bound when by proving . Nikiforov and Khadzhiivanov (1981) and Lovász and Simonovits (1983) independently found for .
I have a conjecture: If G has n vertices, edges, and t_{n,e} triangles, then G^{c} is not connected. Barnhart and I verified this when . If true for all n, one can recursively find t_{n,e}. This would give analytic proofs of all results above plus a new bound similar to Fisher's when .