Ле́ма про ви́далення графа стверджує, що якщо граф містить кілька копій даного підграфа, всі його копії можна виключити видаленням малого числа ребер. Лему іноді називають ле́мою про ви́далення трику́тників у разі, коли підграф є трикутником.

Формулювання
Нехай  — граф з  вершинами. Тоді для будь-якого графа  з  вершинами, який має  ізоморфних  підграфів можна виключити всі ці підграфи, видаливши  ребер з . Тут  означає "o мале".

Доведення та узагальнення
Лему про видалення графа спочатку довели для випадку, коли підграф є трикутником, Імре З. Ружа і Ендре Семереді (1978), використавши лему регулярності Семереді. Пізніше лему розширено на інші типи підграфів — на орієнтовані графи і гіперграфи. Альтернативне доведення, що дає сильніші межі кількості ребер, які потрібно видалити, як функцію числа копій підграфа, опублікував 2011 року Якоб Фокс.

Застосування
Ружа і Семереді сформулювали лему про видалення трикутників, щоб забезпечити підквадратичні верхні межі задачі Ружі — Семереді від розміру графів, у яких будь-яке ребро належить єдиному трикутнику. Лема про видалення графа застосовується в , оскільки з неї випливає, що в будь-якому графі, або граф майже вільний від графа , або випадковими вибірками легко знайти копію  у графі. Лему про видалення гіперграфа можна використати для доведення теореми Семереді про існування довгих арифметичних прогресій у щільних підмножинах цілих чисел.

Примітки



