The blow-up lemma essentially says that regular pairs in Szemerédi's regularity lemma behave like complete bipartite graphs from the point of view of embedding bounded degree subgraphs.

In particular, given a graph of order , minimal vertex degree and maximal vertex
degree ,
then there exists an
such that the following holds. Let be an arbitrary positive integer, and replace the vertices
of with pairwise disjoint -sets , , ..., (blowing up). Now construct two graphs on the same vertex
set .
The graph
is obtained by replacing all edges of with copies of the complete bipartite graph , and construct a sparser graph by replacing the edges
of with some -superregular pair. If a graph with is embeddable into , then it is already embeddable into (Komlós *et al. *1998).