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.