Take the 2-minute tour ×
MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

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)?

share|improve this question

2 Answers 2

up vote 10 down vote accepted

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 .

share|improve this answer

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.

share|improve this answer

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

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