Given $n$, the number of vertices, what is the number of triangle-free simple graphs on $n$ vertices (or asymptotically)?

A more difficult problem is, given $n$, $m$, what is the number of triangle-free simple graphs on $n$ vertices with $\le m$ edges (or asymptotically)?


2 Answers 2


Next terms are 581460254001, 31720840164950 (sent to OEIS). All these numbers were found by exhaustive enumeration. As far as I know, the theoretic enumeration problem is unsolved, even for labelled graphs.

As for asymptotics, it is an old result of Erdős, Kleitman and Rothschild that almost all triangle-free graphs are bipartite. Someone studied the case of restricted numbers of edges see http://onlinelibrary.wiley.com/doi/10.1002/(SICI)1097-0118(199602)21:2%3C137::AID-JGT3%3E3.0.CO;2-S/abstract .


Computing the first terms in sage and searching in OEIS gave A006785 Triangle-free graphs on n vertices

The first terms are:

1, 2, 3, 7, 14, 38, 107, 410, 1897, 12172, 105071, 1262180, 20797002, 467871369, 14232552452

There is no formula in OEIS, some of the referenced papers might be useful.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.