Zdravím, řeším příklad jehož zadání zní:
Existuje bipartitní graf, jehož doplněk je také bipartitní? Pokud ano, najděte všechny takové grafy.
Podle mě žádný takový bipartitní graf neexistuje (intuice). Důkaz jsem zkoušel přes počet hran bipartitního grafu a všech hran na všech vrcholech grafu.
Víme, že bipartitní graf má MxN hran, kde M a N značí počet vrcholů v každé z partit. Všech hran v grafu může být celkem M+N nad 2.
Snažím se ukázat, že počet hran, které zbývají na doplněk, nemůžou spolehlivě ze žádných z dvou vzniklých partit udělat úplný bipartitní graf, ale už nevím jak na to.
Poradí někdo prosím?
Offline