Strona 1 z 1
Własności grafu rzędu 6
: 13 gru 2019, o 21:43
autor: lola456
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ł?
Re: Własności grafu rzędu 6
: 13 gru 2019, o 21:58
autor: Gosda
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).
Re: Własności grafu rzędu 6
: 13 gru 2019, o 22:11
autor: lola456
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).
W takim razie w przypadku gdy wszystkie wierzchołki nie są jego sąsiadami otrzymujemy sprzeczność?