Teoria grafów

[Ewellka1312]

Mam udowodnić takie twierdzenie ale nie wiem od czego zacząć? :
Każdy maksymalny zbiór niezależny grafu \(\displaystyle{ G}\) jest minimalnym zbiorem dominującym tego grafu.

[Mruczek]

Powyższe twierdzenie jest fałszywe.
Weźmy np. graf gwiazdę, czyli drzewo, które ma jeden wierzchołek w korzeniu i jest połączone z \(\displaystyle{ 10}\) wierzchołkami. Maksymalny zbiór niezależny to zbiór liści tego drzewa, ma wielkość \(\displaystyle{ 10}\). Jest on też zbiorem dominującym, ale nie minimalnym, bo minimalny zbiór dominujący tego drzewa składa się z jednego wierzchołka - korzenia.

Prawdziwe jest za to twierdzenie:
Każdy maksymalny zbiór niezależny grafu jest pewnym zbiorem dominującym tego grafu.

Dowód:
Bierzemy ten maksymalny zbiór niezależny. Dowód nie wprost. Przypuśćmy, że nie jest to zbiór dominujący. Wtedy istniałby wierzchołek w tym grafie, który nie jest zdominowany przez ten zbiór niezależny. To znaczy, że ten wierzchołek nie jest sąsiadem żadnego z wierzchołków tego zbioru niezależnego, czyli możemy dodać go do poprzedniego maksymalnego zbioru niezależnego zwiększając zbiór niezależny, sprzeczność.

[Ewellka1312]

Przeanalizowałam definicje i minimalny zbiór dominujący to taki, że po usunięciu wierzchołka już nie będzie zbiorem dominującym zatem to twierdzenie jest prawidłowe.

[Mruczek]

Nie masz racji. Podałem kontrprzykład, więc twierdzenie jest fałszywe.