Pigeon hole

Question

Show that in a group of $n$ people there are two who have identical number of friends in that group.

Answer 1

Case 1: Suppose each of the n members of the group has at least 1 friend.

In this case each of the n members of the group will have 1 to n-1 friends.

Now, consider the numbers from 1 to n-1 as holes and the n members as pegions.

Since there are n-1 holes and n pegions there must exist a hole which must contain more than one pegion.

That means there must exist a number from 1 to n-1 which would contain more than 1 member.

So,in a group of n members there must exist at least two persons having equal number of friends.

Case 2: There exist a person having no friends.

In this case  leaving the person having no friends if any one of the remaining (n-1) friends have zero friends. Then we get two persons having identical number of friends.

Otherwise leaving the person having no friends from the group the remaining (n-1) persons would have 1 to (n-2) friends which is similar to case 1. So, in this case also we would have two persons having identical number of friends.

Hence, in a group of n people there must exist two persons having identical number of friends in that group (Proved).

Answer 2

Consider the n people as n vertices of a graph. If two persons are friends, then the corresponding vertices in the graph has a edge between them..

Now the number of friends of a person is the degree of the corresponding vertex in the graph.

We know that, "in any graph there will be two vertices with same degree" (You can check this by drawing some graphs). Therefore, there must be two persons with same number of friends..