• Definice
• Test

doplněk (komplement) grafu

Graf –G=(V,–E) je doplněk grafu G=(V,E), pokud platí: Hrana {v_i, v_j} náleží do grafu G tehdy a jen tehdy, když {v_i, v_j} nenáleží do grafu –G.

Dva vrcholy v grafu –G jsou sousední právě tehdy, když nejsou sousední v grafu G.

Grafy ABCD a EFGH jsou navzájem svými doplňky