Witam, mam do zrobienia zadanie z teorii grafów.
Uzasadnij, że dowolny graf rzędu 6 zawiera \(\displaystyle{ K3}\) lub \(\displaystyle{ K3'}\) (dopełnienie grafu) jako podgraf indukowany.
Zastanawiam się, czy nie trzeba tutaj użyć zasady szufladkowania natomiast nie za bardzo wiem jak. Czy ktoś ma jakiś pomysł?
Własności grafu rzędu 6
-
Gosda
- Użytkownik
- Posty: 340
- Rejestracja: 29 cze 2019, o 19:46
- Płeć: Mężczyzna
- Lokalizacja: Oulu
- Podziękował: 42 razy
- Pomógł: 60 razy
Re: Własności grafu rzędu 6
Wybierz jeden wierzchołek w tym grafie, albo istnieje trójka pozostałych wierzchołków, które są jego sąsiadami, albo nie są (wszystkie) jego sąsiadami. Bez straty ogólności rozpatrz pierwszy przypadek. Wtedy albo pewne dwa z trzech sąsiadują (i razem z wybranym tworzą graf pełny), albo żadne z nich nie sąsiadują (i wtedy ich dopełnienie tworzy graf pełny).
-
lola456
- Użytkownik
- Posty: 71
- Rejestracja: 16 lis 2019, o 21:50
- Płeć: Kobieta
- wiek: 19
- Podziękował: 36 razy
- Pomógł: 1 raz
Re: Własności grafu rzędu 6
W takim razie w przypadku gdy wszystkie wierzchołki nie są jego sąsiadami otrzymujemy sprzeczność?Gosda pisze: ↑13 gru 2019, o 21:58 Wybierz jeden wierzchołek w tym grafie, albo istnieje trójka pozostałych wierzchołków, które są jego sąsiadami, albo nie są (wszystkie) jego sąsiadami. Bez straty ogólności rozpatrz pierwszy przypadek. Wtedy albo pewne dwa z trzech sąsiadują (i razem z wybranym tworzą graf pełny), albo żadne z nich nie sąsiadują (i wtedy ich dopełnienie tworzy graf pełny).