The random triangle removal process starts with a complete graph and repeatedly deletes the three edges of a uniformly chosen remaining triangle until the graph is triangle-free. All choices are conditional on the current graph. The removed triangles are edge-disjoint and form a partial Steiner triple system, while the terminal edges are its uncovered pairs.
Random Triangle Removal Process
See also
Complete Graph, Random Graph, Steiner Triple System, Triangle-Free GraphExplore with Wolfram|Alpha
References
Bohman, T.; Frieze, A.; and Lubetzky, E. "Random Triangle Removal." Adv. Math. 280, 379-438, 2015. https://doi.org/10.1016/j.aim.2015.04.015.Cite this as:
Weisstein, Eric W. "Random Triangle Removal Process." From MathWorld--A Wolfram Resource. https://mathworld.wolfram.com/RandomTriangleRemovalProcess.html