Udowodnij twierdzenie z teorii grafów

[rafalpw]

Udowodnij, że w grupie \(\displaystyle{ 6}\) osób istnieje taka trójka, w której nikt się nie zna nawzajem lub wszyscy się znają.

Grupę \(\displaystyle{ 6}\) osób traktujemy jako graf o \(\displaystyle{ 6}\) wierzchołkach, a znajomość między dwiema osobami jako krawędź między danymi dwoma wierzchołkami.

Robię tak:

Zakładamy, że nie istnieje taka trójka, w której nikt się nie zna i pokażemy, że musi istnieć taka trójka, w której wszyscy się znają.

Algorytm wygląda następująco:

1) Wybieramy dowolną trójkę wierzchołków i wiemy, że musi tam istnieć przynajmniej jedna krawędź, więc oznaczamy ją \(\displaystyle{ \alpha}\)
2) Bierzemy dowolną trójkę taką, że nie ma w niej dwóch wierzchołków połączonych krawędzią \(\displaystyle{ \alpha}\). W niej też musi istnieć przynajmniej jedna krawędź, więc ją też oznaczamy \(\displaystyle{ \alpha}\)
3) Powtarzamy ten krok aż nie zostanie żadna trójka, w której nie ma krawędzi \(\displaystyle{ \alpha}\)

Wydaje mi się, że ten algorytm jest prawidłowy (czyli wśród tych \(\displaystyle{ 6}\) osób znajdą się \(\displaystyle{ 3}\) takie, że każde \(\displaystyle{ 2}\) z nich będą połączone krawędzią \(\displaystyle{ \alpha}\)), ale nie umiem tego pokazać. Zauważyłem też, że oznaczając w ten sposób krawędzie otrzymamy \(\displaystyle{ 8}\) krawędzi oznaczonych \(\displaystyle{ \alpha}\), chociaż tego też nie umiem udowodnić.

Czy ktoś ma jakieś wskazówki? Albo jakiś alternatywny sposób?

[Qń]

Rozważmy dowolny wierzchołek, nazwijmy go \(\displaystyle{ W}\). Albo jest on połączony krawędzią z pewnymi trzema z pozostałych wierzchołków, albo też niepołączony z pewnymi trzema. Nazwijmy je \(\displaystyle{ A,B,C}\)

W pierwszym wypadku jeśli istnieje jakaś krawędź pomiędzy \(\displaystyle{ A,B,C}\) np. \(\displaystyle{ AB}\), to \(\displaystyle{ A,B,W}\) są parami połączone krawędzią, czyli koniec. Jeśli zaś nie istnieje, to \(\displaystyle{ A,B,C}\) nie są połączone żadną krawędzią tylko też koniec. Drugi przypadek analogicznie.

Q.