Pokaż, że istnieje taka grupa pięciu osób, w której nie ma ani trzech osób znających się
nawzajem, ani trzech osób takich, że żadna z nich nie zna dwóch pozostałych.
Jak na razie doszedłem do tego, że \(\displaystyle{ 1 \le deg(v) \le 2}\) dla każdego wierzchołka (graf musi być spójny i żaden wierzchołek nie może mieć co najmniej 3 krawędzi, bo wtedy nie byłyby spełnione 2 warunki zadania jednocześnie. Natomiast rysowałem ten graf na milion sposobów i nie mogłem znaleźć takiego, który spełnia to, do czego doszedłem i warunków zadania.
Teoria grafów - zasada szufladkowa Dirichleta
-
- Użytkownik
- Posty: 1114
- Rejestracja: 26 paź 2008, o 19:43
- Płeć: Mężczyzna
- Podziękował: 23 razy
- Pomógł: 157 razy
Re: Teoria grafów - zasada szufladkowa Dirichleta
Masz poprawne obserwacje.
Weź cykl składający się z \(\displaystyle{ 5}\) wierzchołków. Nie zawiera on trójkątów (oczywiste). Nie zawiera też zbioru niezależnego składającego się z \(\displaystyle{ 3}\) wierzchołków. Można to pokazać rozpatrując wszystkie przypadki, albo w ten sposób:
Przypuśćmy, nie wprost, że zawiera taki zbiór niezależny. Niech bso. wierzchołek \(\displaystyle{ A}\) do niego należy, wtedy żaden z jego sąsiadów \(\displaystyle{ B}\) i \(\displaystyle{ C}\) do niego nie należy, czyli musiałyby do niego należeć dwa pozostałe wierzchołki tego cyklu, czyli \(\displaystyle{ D}\) i \(\displaystyle{ E}\), ale one są połączone krawędzią, sprzeczność.
Weź cykl składający się z \(\displaystyle{ 5}\) wierzchołków. Nie zawiera on trójkątów (oczywiste). Nie zawiera też zbioru niezależnego składającego się z \(\displaystyle{ 3}\) wierzchołków. Można to pokazać rozpatrując wszystkie przypadki, albo w ten sposób:
Przypuśćmy, nie wprost, że zawiera taki zbiór niezależny. Niech bso. wierzchołek \(\displaystyle{ A}\) do niego należy, wtedy żaden z jego sąsiadów \(\displaystyle{ B}\) i \(\displaystyle{ C}\) do niego nie należy, czyli musiałyby do niego należeć dwa pozostałe wierzchołki tego cyklu, czyli \(\displaystyle{ D}\) i \(\displaystyle{ E}\), ale one są połączone krawędzią, sprzeczność.