Filtr seznamu úloh?

Zvolte požadované hodnoty úrovní a požadované štítky. V obsahu budou zobrazeny pouze úlohy mající jednu ze zvolených úrovní každé škály a alespoň jeden štítek. Pokud chcete filtrovat pouze podle některých škál nebo jen podle štítků, nechte ostatní skupiny prázdné.

Škály

Obtížnost

Štítky

Typ úlohy
«
«
«

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