Among the collections of the open problems of Paul Erdős on the website of
Professor Fan Chung, there is one called "number of triangle-free graphs".


<http://www.math.ucsd.edu/~erdosproblems/erdos/newproblems/NumberOfTriangleFreeGraphs.html>


Open Problem: Determine or estimate the number of maximal triangle-free graphs
on $n$ vertices.


Is any one working on this problem? Any known related results? 


Now I am considering about using a "connection game" method to solve this problem: Given a set of $n$ players, each one chooses to connect to other nodes, if any two neighbors of it connect a new edge(which means there would form a triangle), it has to choose delete either edges with those two neighbors. Then the question is how many different topology connections does it have? 


Any comments on this method? 



Determine or estimate the number of maximal triangle-free graphs on $n$ vertices
By Theorem 1 in the paper of [Erdős, Kleitman, and Rothschild](http://www.renyi.hu/~p_erdos/1976-03.pdf), the number of triangle-free graphs on $n$ vertices is $2^{n^2(1/4 +o(1)) }$. The number of bipartite graphs with a fixed pair of parts of size $n/2$ is $2^{n^2/4}$. Here is a construction of $2^{n^2(1/8 +o(1)) }$ maximum triangle-free graphs. 


Suppose we start with a bipartite graph on two parts $A$ and $B$. We'll try to embed this in a maximal triangle-free graph with $2|A|+|B|$ vertices. For every vertex $a \in A$, add a vertex $a'$ connected to $a$ and every element of $B$ not connected to $a$. This graph is triangle-free, but not necessarily maximal. 


Adding an edge between two elements of $A$ will form a triangle with any mutual neighbor in $B$. Such a mutual neighbor will exist for almost all bipartite graphs as long as $\log |A| \ll |B|$. Similarly, an edge between two elements of $B$ will form a triangle with any mutual neighbor in $A$, which will usually exist (proportion approaching $1$) if $\log |B| \ll |A|$.


Adding an edge between $a'$ and a neighbor $b$ of $a$ forms the triangle $a-b-a'$, as does adding an edge between $a$ and an element $b\in B$ initially not connected to $a$. 


Adding an edge between $a\_0'$ and $a\_1 \in A$ will form a triangle as long as there is some $b\in B$ connected to $a\_1$ but not $a\_0$. Again, this happens with a proportion approaching $1$ if $\log|A| \ll |B|$. 


By the way, it's not a problem if you can add more edges between $a\_0'$ and elements of $A$. If you can, do so. The important thing is that we ensured that no edges between elements of $A \cup B$ can be added without forming triangles, and we did so by adding a small number of vertices.


Adding edges between the added vertices might or might not form triangles. Add enough edges to make the graph maximal. Assuming the high-proportion conditions are satisfied, there is at least one maximal graph so that the induced subgraph on $A \cup B$ is the original bipartite graph. 


Choose $|B| = 2|A|$. As $|A| \to \infty$, a proportion approaching $1$ of these bipartite graphs can be embedded in a maximal triangle-free graph on $4|A|$ vertices. This constructs $2^{n^2(1/8 + o(1))}$ maximal triangle-free graphs on $n$ vertices, or roughly the square root of the total number of triangle-free graphs.


