Matematyka.pl

Pokazać, że wśród \(\displaystyle{ n}\) osób \(\displaystyle{ (n \ge 2)}\) istnieją takie dwie osoby, które znają tę samą liczbę osób (w tej grupie). Zakładamy, że relacja znajomości jest symetryczna.

Nie wiem jak to zrobić. Wydaje mi się, że można by to jakoś pokazać z zasady szufladkowej, ale nie wiem do końca jak.
Zadanie jest związane z grafami.

Niech G - graf prosty o \(\displaystyle{ n}\) wierzchołkach, \(\displaystyle{ deg(v)}\) - stopień wierzchołka grafu G, który oznacza ile osób zna \(\displaystyle{ v}\).
Załóżmy nie wprost, że nie istnieją dwa wierzchołki o tym samym stopniu.
Największy możliwy stopień wierzchołka to \(\displaystyle{ n-1}\), bo graf jest prosty i ma n wierzchołków.
Wtedy \(\displaystyle{ n-1, n-2, n-3, ..., 1, 0}\) jest jedynym możliwym ciągiem stopni wierzchołków tego grafu.
Teraz już łatwo pokazać, że taki ciąg stopni nie jest graficzny.