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).

Obtížnost: Snadná úloha (řešená úvahou nebo přímo z definic)
Úloha na dokazování, ověřování
En translation
	Zaslat komentář k úloze