Given $n$, the number of vertices, what is the number of labeled trianglefree graphs on $n$ vertices?
2 Answers
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 trianglefree graphs are bipartite. Proemel, Schickinger and Steger refined this to show that almost all trianglefree 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 ProemelSchickingerSteger 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).
user36212 has already essentially answered the question; the state of the art has not yet been pointed out though (by that I mean I miss a mention of the latest relevant publications, and a mention of the hypergraph container method, which the OP might find useful being told about) : due to work of Balogh and coworkers also for the class of maximal trianglefree graphs the asymptotics are known (and these differ from the asymptotics for all trianglefree graphs). In
[BP2014] József Balogh, Šárka Petříková, Number of maximal trianglefree graphs, Bull. London Math. Soc. 46(5) (2014), 10031006
it was shown that the lower bound of $2^{\frac18 n^2 + o(n^2)}$ for labelled maximal trianglefree graphs does give the correct asymptotics (to within this precision).
Incidentally, while [BP2014] avers without reference that the lower bound was "known much earlier", the first public reference seems to be this answer of Douglas Zare, which gives the a slighly more complicated construction than [BP2014], but in return gives a little more detail regarding the proof that the construction actually produces enough maximal trianglefree graphs. An exposition giving full detail does not exist as far as I know, though writing one would be easy: for the construction in [BP2014], that is, if one takes a pefect matching $M$ consisting of $n/4$ edges, and adds a new independent set $S$ of $n/2$ vertices, and then decides independently for each $(u,vw)\in S\times M$ whether to join $u$ to $v$ or to $w$ (and does exactly one of those), then evidently in the labelled sense precisely $2^{\frac{n}{2}\cdot\frac{n}{4}}=2^{n^2/8}$ are constructed, and what remains to be proved is that $2^{n^2/8  r}$ with $r\in o(n^2)$ of those are maximal trianglefree; this is an exercise.
The proof of the upper bound in [BP2014] uses a result of Saxton and Thomason sometimes referred to a the method of hypergraph containers.
One should note that, in view of the results from the 1970s already mentioned by user36212, [JP2014] implies
$\text{# maximal trianglefree graphs}\qquad\sim_{n\to\infty}\qquad\sqrt{\text{# triangle free graphs}}$.
Even more recently, in
[BLPS2015] József Balogh, Hong Liu, Šárka Petříková, Maryam Sharifzadeh,
The Typical Structure of Maximal TriangleFree Graphs,
Forum of Mathematics, Sigma (2015), Vol. 3, e20, 19 pages
two structural statements were proved, 'structural' in the sense that they shed some light on how most of the members of the set $\mathbb{K}$ of finite maximal trianglefree graphs 'look' like:
(0) Almost every member of $\mathbb{K}$ can be constructed according to what arguably is the most straighforward construction of a maximal trianglefree graph: to start with a perfect matching $M$, to add an independent set $S$, and then to add edges between $V(M)$ and $S$ until the graph is maximaltriangle free. (Evidently, not every member of $\mathbb{K}$ can be so constructed: e.g., the Petersen graph cannot.)
(1) By [BLPS2015, Lemma 2.4],
$\forall n\in\omega$ $\forall$ maximal trianglefree $n$vertex graph $G$
($\#\text{maximal independent sets in $G$}$)
$\leq$
$2^{\frac12 n  \frac{1}{25}\text{number of vertexdisjoint threevertex paths in $G$}}$
It seems not to be known whether there is any trianglefree graph for which the bound in the above lemma is attained.

$\begingroup$ What is their reference for the "decades old" lower bound? $\endgroup$ Commented Feb 3, 2018 at 0:01

1$\begingroup$ @DouglasZare: their reference is mathoverflow.net/q/159494, without mentioning your answer therein. I searched the literature much, and I asked around, and by now I think it is most likely that that answer of yours is the first published reference for the lower bound. I will edit accordingly. I think that they should have mentioned you, but the behavior is well within what is acceptable (and perhaps they thought it more polite to not do so). My 'decadesold' was an example of en.wikipedia.org/wiki/False_precision, and it happened by writing in a hurry; I will change that, too. $\endgroup$ Commented Feb 6, 2018 at 6:26