Triangle in a graph ($K_3$)

A triangle is a set of three vertices joined by all three possible edges, equivalently a copy of $K_3$.

A family of triangles in a graph is edge-disjoint if no edge belongs to two members. Any deletion of edges producing a triangle-free graph must remove at least one distinct edge for each member. The triangles in a graph may share vertices.

The triangle count of a finite simple graph is the number of unordered triples of vertices inducing a triangle in a graph. In a tripartite graph with parts $X,Y,Z$ and adjacency indicator functions $g_{XY},g_{YZ},g_{XZ}$, it equals $|X||Y||Z|{\mathbb{E}}_{x,y,z}{g}_{XY}(x,y)g_{YZ}(y,z)g_{XZ}(x,z)$, using uniform expectations on nonempty parts.

A triangle-free graph contains no triangle.

If every edge of a graph lies in at least one triangle, then the number of triangles is at least one third of the number of edges. Count edge-triangle incidences: each edge contributes at least one and each triangle contributes three.