Teoria grafów - zasada szufladkowa Dirichleta

[jakub1998]

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.

[Mruczek]

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ść.