Blow-Up 引理

Blow-up 引理本质上说明，塞迈雷迪正则性引理中的正则对的行为类似于完全二部图，从嵌入有界度子图的角度来看。

特别地，给定一个阶为的图，最小顶点度和最大顶点度，那么存在一个，使得以下成立。设为任意正整数，并将的顶点替换为两两不相交的-集, , ..., （blow-up）。现在在相同的顶点集上构造两个图。图是通过将的所有边替换为完全二部图的副本而获得的，并通过将的边替换为一些-超正则对来构造一个更稀疏的图。如果一个图，其中可以嵌入到中，那么它也已经可以嵌入到中 (Komlós et al. 1998)。