Дополнение графа ( обратный граф ) — граф ${\displaystyle G'}$ , имеющий то же множество вершин, что и заданный граф ${\displaystyle G}$ , но в котором две несовпадающие вершины смежны тогда и только тогда , когда они не смежны в ${\displaystyle G}$ .

Формально для простого графа ${\displaystyle G=(V,E)}$ и ${\displaystyle K={\mathcal {P}}(V^{2})}$ — множества всех двухэлементных подмножеств его вершин — дополнение ${\displaystyle G'}$ определяется как пара ${\displaystyle (V,K\setminus E)}$ — граф с исходным набором вершин и с набором ребёр, полученным из полного графа удалением имевшихся в заданном графе.

Дополнение пустого графа (содержащего только вершины, но не рёбра) является полным графом , и наоборот. Независимое множество графа является кликой в дополнении графа, и наоборот. Дополнение любого графа без треугольников не содержит клешней .

Самодополнительный граф — это граф, который изоморфен своему дополнению. Кографы определяются как графы, которые можно построить из единственной точки несвязанным объединением и операцией дополнения. Кографы образуют семейство самодополнительных графов — дополнение любого кографа является другим (возможно, отличным от исходного) кографом.

Литература

• Харари Ф. Теория графов. — 2-е издание. — М. : УРСС, 2003. — 295 с. — ISBN 5-354-00301-6 .