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.
Grafy, osoby znające tę samą liczbę osób w grupie
-
Andreas
- Użytkownik
- Posty: 1130
- Rejestracja: 1 lis 2008, o 22:33
- Płeć: Mężczyzna
- Podziękował: 72 razy
- Pomógł: 156 razy
Grafy, osoby znające tę samą liczbę osób w grupie
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.
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.