In order to determine properties of all triangle-free graphs, it often suffices to investigate maximal triangle-free graphs. These are triangle-free graphs for which the insertion of any further edges would create a triangle. For triangle-free graphs of order n ≥ 3 being maximal triangle-free is equivalent to having diameter 2.
Maximal triangle-free graphs can also be used to determine the triangle Ramsey numbers R(K3, G) (see [1,2]). Various triangle Ramsey graphs are also present in the searchable database and can be found by searching for the keyword 'ramsey'.
The graph lists are currently only available in 'graph6' format. The larger files are compressed with gzip.
All numbers were independently confirmed by MTF and triangleramsey . The counts for 24 vertices were computed with triangleramsey in [3].
Vertices | No. of graphs |
---|---|
3 | 1 |
4 | 2 |
5 | 3 |
6 | 4 |
7 | 6 |
8 | 10 |
9 | 16 |
10 | 31 |
11 | 61 |
12 | 147 |
13 | 392 |
14 | 1274 |
15 | 5036 |
16 | 25617 |
17 | 164796 |
18 | 1337848 |
19 | 13734745 |
20 | 178587364 |
21 | 2911304940 |
22 | 58919069858 |
23 | 1474647067521 |
24 | 45599075629687 |
[1] S. Brandt, G. Brinkmann and T. Harmuth, All Ramsey numbers r(K3,G) for connected graphs of order 9, Electron. J. Combinatorics, 5, R7, 1998.
[2] G. Brinkmann, J. Goedgebeur and J.C. Schlage-Puchta, Ramsey numbers R(K3,G) for graphs of order 10, Electronic Journal of Combinatorics, 19(4), 2012.
[3] J. Goedgebeur, On minimal triangle-free 6-chromatic graphs, Journal of Graph Theory, 93(1):34-48, 2020.