= Triangle deletion in the alteration method
If a graph has $E$ edges and $T$ triangles, successively delete one edge from a remaining triangle. No new triangle is created and at most $T$ deletions are needed, so a triangle-free subgraph has at least $E-T$ edges. A random-graph expectation lower bound on $E-T$ therefore proves existence of a large triangle-free graph. With edge probability $n^{-1/2}$, the expectation is $(n^2-1)/(3\sqrt n)$; this is a useful existence bound but is not within a constant factor of the sharp quadratic <Mantel theorem> bound.
Back to article page
