trianglefree

Trianglefree is a property of a simple graph; a trianglefree graph contains no subgraph isomorphic to a triangle (K3). In other words, it has no 3-cycle.

All bipartite graphs are trianglefree, since bipartition forbids odd cycles. The converse is false: graphs such as the cycle C5 are trianglefree but not bipartite.

Examples include trees (which are acyclic), cycles of length at least 4 such as C4, and complete bipartite graphs K_{m,n}. The class is closed under taking subgraphs; removing edges or vertices preserves the trianglefree property.

One central result is Mantel's theorem: among all trianglefree graphs on n vertices, the maximum possible number of edges is floor(n^2/4), achieved by a complete bipartite graph with parts as equal as possible. This is the r=3 case of Turán's theorem, and the extremal number ex(n, K3) equals floor(n^2/4).

Trianglefree graphs play a role in extremal graph theory and Ramsey theory; for instance, they provide constructions with high edge density avoiding triangles, and relate to bounds on Ramsey numbers such as R(3,t).