Triangle-Free Graph

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 simple graph on graph vertices has at most graph edges, with equality exactly for the complete bipartite graph , where and denote the floor function and ceiling function, respectively.

The numbers of triangle-free simple graphs, up to graph isomorphism, 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 connected simple graphs, up to graph isomorphism, on , 2, 3, ... nodes are 1, 1, 1, 3, 6, 19, 59, 267, ... (OEIS A024607), the first few of which are illustrated above.

For a triangle-free graph on vertices, the least eigenvalue of its signless Laplacian matrix satisfies (Cai et al. 2026). The Higman-Sims graph and its balanced blow-ups attain equality. Cai et al. (2026) report GPT-6.1 Sol assistance with the proof and verification code.

Tuza's conjecture asks whether every simple graph can be made triangle-free by deleting at most twice its maximum number of pairwise edge-disjoint triangles. Kandasamy (2026) proved this for maximum vertex degree at most 10, with disclosed AI assistance in code and part of a proof lemma.