Doplněk bipartitního grafu

Úloha číslo: 3572

Existuje bipartitní graf s aspoň \(5\) vrcholy, jehož doplněk je také bipartitní?

  • Řešení

    Nikoli, jedna z částí obsahuje alespoň tři vrcholy a v doplňku tyto tři vrcholy tvoří trojúhelník.

    Graf obsahující trojúhelník nemůže být bipartitní, protože dva z těchto vrcholů by musely být ve stejné části.

  • Odpověď

    Takový graf neexistuje.

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