G5

[flosko]

Es seien n Personen in der Gruppe. Wenn keine zwei Personen die gleiche Anzahl von Freunden haben, so gibt es genau eine Person, die keinen Freund hat, eine Person, die einen Freund hat, eine Person mit zwei Freunden, etc. Schließlich gibt es auch eine Person, die n-1 Freunde hat, also mit jedem in der Gruppe befreundet ist. Dies steht aber im Widerspruch dazu, dass es eine Person gibt, die mit niemandem befreundet ist und somit muss es mindestens zwei Personen mit der gleichen Anzahl von Freunden geben.