MathOverflow is a question and answer site for professional mathematicians. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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|cite|improve this question
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;2-S/abstract .

share|cite|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|cite|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.