Answer to Question #143741 in Discrete Mathematics for Jayshree

Question

There are some people (more than 1 person) in a party. Prove that 2 of them have the same number of friends in the party ( Hint: friendship is a mutual relation)

Answer 1

Let n be the number of people in a party.

The maximum number of friends that 1 person can have is n-1. Because if person has n friends, it means he is a friend with himself.

If all people have different number of friends, it means 1 person has 0 friends, 1 person has 1 friend, ... 1 person has n-1 friends. Person with n-1 friends should be a friend with each other, but a person with 0 friend is not a friend with somebody. Сontradiction. It means some people have the same number of friends.