Теорема о совершенных графах Ловаша[1][2] утверждает, что неориентированный граф является совершенным тогда и только тогда, когда его дополнение также совершенно. Это утверждение высказал в виде гипотезы Берж[3][4] и утверждение называют иногда слабой теоремой о совершенных графах, чтобы не смешивать со строгой теоремой о совершенных графах[5], описывающей совершенные графы их запрещёнными порождёнными подграфами.
Совершенный граф — это неориентированный граф, в любом порождённом подграфе которого размер его наибольшей клики равен минимальному числу цветов раскраски подграфа. Совершенные графы включают много важных классов графов, куда входят двудольные графы, хордальные графы и графы сравнимости.
Дополнение графа имеет ребро между двумя вершинами тогда и только тогда, когда исходный граф такого ребра не имеет. Таким образом, клика в исходном графе становится независимым множеством в дополнении и раскраска исходного графа становится кликовым покрытием дополнения.
Эквивалентная формулировка: В совершенном графе размер наибольшего независимого множества равен минимальному числу клик в кликовом покрытии.
Пусть G — граф-цикл нечётной длины, большей трёх (так называемая «нечётная дыра»). Тогда требуется для любой раскраски G по меньшей мере три цвета, но нет ни одного треугольника, так что граф не совершенен. По теореме о совершенных графах, дополнение графа G («нечётная антидыра») должно поэтому также быть несовершенным. Если граф G является циклом из пяти вершин, он изоморфен своему дополнению, но это неверно для более длинных циклов. Нетривиальной задачей является вычисление кликового числа и хроматического числа в нечётной антидыре и нечётной дыре. Как утверждает строгая теорема о совершенных графах, нечётные дыры и нечётные антидыры оказываются минимальными запрещёнными порождёнными подграфами совершенных графов.
В нетривиальном двудольном графе оптимальное число цветов (по определению) равно двум, и (поскольку двудольные графы не содержат треугольников) наибольший размер клики равен также двум. Таким образом, любой порождённый подграф двудольного графа остаётся двудольным. Таким образом, двудольные графы являются совершенными. В двудольных графах с n вершинами наибольшее покрытие кликами принимает форму наибольшего паросочетания вместе с дополнительной кликой для каждой непокрытой вершины с размером n − M, где M — число элементов в паросочетании. В этом случае из теоремы о совершенных графах следует теорема Кёнига, что размер максимального независимого множества в двудольном графе в двудольном графе также равно n − M[6], результат, который был главным стимулом формулировки Бержем теории совершенных графов.