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.
