graf samodopełniający

Samodopełniający się graf (ang. self-complementary graph) to graf, który jest izomorficzny do swojego dopełnienia. Najprostszym samodopełniającym się grafem jest 4-wierzchołkowa ścieżka oraz 5-wierzchołkowy cykl. N-wierzchołkowy samodopełniający się graf ma dokładnie połowę krawędzi grafu pełnego, to jest n(n − 1)/4 krawędzi i (jeżeli posiada więcej niż jeden wierzchołek) ma średnicę o rozmiarze 2 lub 3.Ponieważ n(n −1) musi być podzielne przez 4, n musi przystawać modulo 4 do 0 lub 1. Na przykład 6-wierzchołkowy graf nie może być samodopełniający się.