Given $n$, the number of vertices, what is the number of labeled triangle-free graphs on $n$ vertices?



Counting labeled triangle-free graphs on $n$ vertices
There shouldn't be any sensible exact formula, as Ira Gessel says.
But there are very good asymptotics and a structural description.


An old result of Erdős, Kleitman and Rothschild is that almost all triangle-free graphs are bipartite. Proemel, Schickinger and Steger refined this to show that almost all triangle-free graphs which are not bipartite can be made bipartite by removing one edge; and almost all of the rest can be made bipartite by removing two edges; and so on.


It's easy to count bipartite graphs (there are roughly $2^{n+n^2/4}$; you can easily enough find accurate asymptotics which depend on the parity of $n$) and similarly the Proemel-Schickinger-Steger classes are not too hard to enumerate asymptotically (I don't know of these being explicitly in the literature).


There are also similar results if you fix the number of edges (which get less precise for sparse graphs).


