TOPICS
Search

Triangle-Free Graph


Triangle-FreeGraphs

A triangle-free graph is a graph containing no graph cycles of length three. A simple graph is triangle-free iff Tr(A^3)=0, where A is the adjacency matrix of the graph and Tr is the matrix trace.

The numbers of triangle-free simple graphs on n=1, 2, 3, ... nodes are 1, 2, 3, 7, 14, 38, 107, 410, 1897, ... (OEIS A006785), the first few of which are illustrated above.

Triangle-FreeConnectedGraphs

The numbers of triangle-free simple connected graphs on n=1, 2, 3, ... nodes are 1, 1, 1, 3, 6, 19, 59, 267, ... (OEIS A024607), the first few of which are illustrated above.


See also

Graph Cycle, Grötzsch Graph, Mycielski Graph, Square-Free Graph, Triangular Graph

Explore with Wolfram|Alpha

References

Sloane, N. J. A. Sequences A006785/M0841 and A024607 in "The On-Line Encyclopedia of Integer Sequences."

Referenced on Wolfram|Alpha

Triangle-Free Graph

Cite this as:

Weisstein, Eric W. "Triangle-Free Graph." From MathWorld--A Wolfram Web Resource. https://mathworld.wolfram.com/Triangle-FreeGraph.html

Subject classifications