В теорії графів, доповнення або обернений до графа G — граф H на тих самих вершинах, поєднаних ребрами тоді і тільки тоді, коли вони несуміжні в G. Тобто, для побудови доповнення графа, потрібно додати всі ребра, необхідні для отримання повного графа і видалити всі ребра, які були присутні до того. Однак, це не доповнення множини графа; доповнені тільки ребра.
Формальна побудова Нехай G = (V, E) буде простим графом і нехай K складається з усіх 2-елементних підмножин V. Тоді H = (V, K \ E) — доповнення G.
Застосування і приклади Декілька концепцій теорії графів стосуються одна одної через доповнення графів: Доповнення безреберного графа це повний граф і навпаки. Незалежна множина в графі це кліка в доповненні графа і навпаки. Доповнення будь-якого графа без трикутників це граф без кігтів. Самодоповняльний граф це граф, який ізоморфний до свого доповнення. Кографи визначені як графи, які можна утворити з диз'юнктного об'єднання і операцій доповнення, і які формують сім'ю самодоповнювальних графів: доповненням будь-якого кографа є інший (можливо, відмінний від початкового) кограф.
Посилання , pages 6 and 29. . Electronic edition , page 4.