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