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.
By Mantel's theorem, a triangle-free graph on 
graph vertices has at most 
graph edges, with equality
exactly for the complete bipartite graph ![K_(|_n/2_|,[n/2])](/images/equations/Triangle-FreeGraph/Inline6.svg)
, where 
and ![[x]](/images/equations/Triangle-FreeGraph/Inline8.svg)
denote the floor function
and ceiling function, respectively.
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.
