Udowodnij, że graf i jego dopełnienie nie mogą być jednocześnie grafami niespójn Lukasz: Udowodnij, że graf i jego dopełnienie nie mogą być jednocześnie grafami niespójnymi. Pomógłby ktoś z tym zadankiem? Ja próbowałem ale nie umiem, nic nie mogę wymyśleć jak do tego podejść. Wiem że ten dowód jest spełniony, mam w głowie jakiś plan ale nie mogę go dać na kartkę

kerajs: Niech graf będzie niespójny. Wybieram dowolny jego spójny podgraf rozłączny z pozostałymi wierzchołkami. W dopełnieniu grafu każdy wierzchołek wybranego podgrafu będzie połączony z pozostałymi wierzchołkami, więc owo dopełnienie będzie spójne.

Lukasz: @kerajs, to jest ten "plan" który widzę, czy tam mam w głowie, ale podejrzewam że na egzaminie musiałbym to jakoś raczej udowodnić bardziej, niż słowami. Czy da sięto jakoś przedstawić ? np indukcyjnie czy jakkolwiek? czy może wydaje ci się że tak wystarczy jeśli to opisze ? (oczywiście jeszcze zapytam o to ćwiczeniowca ale to dopiero w tygodniu)