A fundamental structural result in extremal graph theory due to Szemerédi (1978). The regularity lemma essentially says that every graph can be well-approximated by the union of a constant number of random-like bipartite graphs, called regular pairs.
Szemerédi's Regularity Lemma
See also
Blow-Up Lemma, Extremal Graph Theory, Seymour Conjecture, Szemerédi's TheoremExplore with Wolfram|Alpha
References
Komlós, J. and Simonovitas, M. "Szemerédi Regularity Lemma and Its Applications in Graph Theory." In Combinatorics, Paul Erdős is Eighty, Vol. 1 (Ed. D. Miklós, V. T. Sós, and T. Szőnyi). Budapest: János Bolyai Mathematical Society, pp. 295-352, 1993.Komlós, J.; Sárkőzy, G. N.; and Szemerédi, E. "Proof of the Seymour Conjecture for Large Graphs." Ann. Comb. 2, 43-60, 1998.Szemerédi, E. "Regular Partitions of Graphs." In Problèmes combinatoires et théorie des graphes (Colloq. Internat. CNRS, Univ. Orsay, Orsay, 1976). Paris: Éditions du Centre National de la Recherche Scientifique (CNRS), pp. 399-401, 1978.Referenced on Wolfram|Alpha
Szemerédi's Regularity LemmaCite this as:
Weisstein, Eric W. "Szemerédi's Regularity Lemma." From MathWorld--A Wolfram Web Resource. https://mathworld.wolfram.com/SzemeredisRegularityLemma.html