A triangle-free graph is a graph containing no graph cycles of length three. A simple graph is triangle-free iff , where is the adjacency matrix of the graph and is the matrix trace.
The numbers of triangle-free simple graphs on , 2, 3, ... nodes are 1, 2, 3, 7, 14, 38, 107, 410, 1897, ... (OEIS A006785), the first few of which are illustrated above.
The numbers of triangle-free simple connected graphs on , 2, 3, ... nodes are 1, 1, 1, 3, 6, 19, 59, 267, ... (OEIS A024607), the first few of which are illustrated above.