Izomorfismus doplňků
Úloha číslo: 3573
Dokažte, že dva grafy jsou izomorfní právě tehdy, když jsou izomorfní jejich doplňky.
Řešení
Protože izomorfismus zachovává hrany i nehrany v původních grafech, tedy zachovává i nehrany v doplňcích (díky zachovávání hran) i hrany v doplňcích (díky zachovávání nehran).