matematykaszkolna.pl
grafy mat123: Udowodnij, że dowolny graf rzędu 6 zawiera K3 lub K3 jako graf indukowany. Robię to tak, że wybieram jeden wierzchołek i teraz mam 2 przypadki. Albo istnieje taka 3 pozostałych wierzchołków, które sąsiadują z moim wybranym wierzchołkiem. Lub przypadek drugi, kiedy nie istnieje taka trójka. Dla 1−ego przypadku pewne dwa z trzech sąsiadują z moim wybranym wierzchołkiem i tworzą graf pełny. Natomiast co będzie w 2−gim przypadku? Wychodzi na to, że żadne z nich nie sąsiadują? I jeżeli tak to co w związku z tym?
14 gru 18:34
Pytający: Zacznij od poprawnego rozpatrzenia pierwszego przypadku. Masz w nim przecież zapewnione, że "istnieje taka 3 pozostałych wierzchołków, które sąsiadują z moim wybranym wierzchołkiem", zatem oczywistym jest, że "pewne dwa z trzech sąsiadują z moim wybranym wierzchołkiem" (a nawet każde 2 z tych 3), jednak nie wiadomo skąd wniosek, że "tworzą graf pełny".
14 gru 18:58
mat123: rysunekCzyli moja sytuacja wygląda tak.(Wybrany wierzchołek jest czerwony) I teraz muszę udowodnić że istnieje ta niebieska krawędź?
14 gru 19:16
mat123: No to jeżeli taka krawędź nie istnieje => dla pozostałych 2 wierzchołków z 1 z wierzchołka z "wybranych" istnieje K3 W przeciwnym przypadku, gdy niebieska krawędź istnieje => istnieje K3 Coś takiego?
14 gru 19:29
Pytający: Tak, coś na tej zasadzie. Jeśli istnieje krawędź pomiędzy dowolnymi 2 z tych 3 sąsiadujących z wybranym, to te 2 i ten wybrany tworzą K3. Jeśli taka krawędź nie istnieje, to te 3 wierzchołki sąsiadujące tworzą dopełnienie K3.
14 gru 19:37
Pytający: A w drugim przypadku istnieją 3 wierzchołki niesąsiadujące z wybranym i reszta rozumowania jest analogiczna do pierwszego przypadku (tylko na odwrót).
14 gru 19:39
mat123: Dziękuję za pomoc
14 gru 19:57
mat123: Zastanawiam się tak teraz, czy rząd tego grafu ma jakieś znaczenie czy zachodzi to również dla grafu rzędu 4? Bo tak naprawdę to nie wykorzystujemy pozostałych dwóch wierzchołków
18 gru 18:22
mat123: Chodzi mi o to, że nie widzę momentu, gdzie była zastosowana tutaj zasada szufladkowania.
18 gru 18:33
Pytający: rysunek Masz 6 wierzchołków, więc poza wybranym wierzchołkiem jest 5 pozostałych wierzchołków. Wśród nich każdy sąsiaduje z wybranym lub nie (znaczy masz 5 elementów należących 2 zbiorów). Zatem musi istnieć zbiór mający co najmniej 3 elementy (znaczy musi zachodzić pierwszy lub drugi przypadek podany wyżej). Dla grafu rzędu 4 nie ma takiej pewności, przykład na rysunku. I zasada szufladkowa, nie szufladkowania.
18 gru 21:02
mat123: Teraz rozumiem emotka i dziękuję za pomoc oraz za poprawienie emotka
18 gru 21:22
mat123: A czy w drugim przypadku w obu "podprzypadkach" nie powstaje dopełnienie K3. Nie powstaje wcale K3?
18 gru 22:32