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.

Choose $n=d^7$ and a binomial random graph of edge probability $d/n$. With high probability its maximum degree is at most $2d$, it has $o(n)$ triangles, and every independent set has size at most $4n\log d/d$. Delete one vertex per triangle. The resulting triangle-free graph has chromatic number at least $d/(8\log d)$. Appending a disjoint star of degree $2d$, if necessary, makes the maximum degree exactly $2d$ without lowering the chromatic number. Thus the order $\Delta /\log \Delta$ is unavoidable.

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.