Show that in any group of people, two of them have the same number of friends in the group. (Some important assumptions here: no one is a friend of him - or herself, and friendship is symmetrical-if x is a friend of y then y is a friend of x.)

Question

Oliver Duran

Mathematics

23 July, 21:42

Show that in any group of people, two of them have the same number of friends in the group. (Some important assumptions here: no one is a friend of him - or herself, and friendship is symmetrical-if x is a friend of y then y is a friend of x.)

+2

Answers (1)

Know the Answer?

Dominique Choi · Answer 1

Step-by-step explanation:

Let us assume there are n people in the group. If possible let each have different number of friends.

Number of friends can vary from 0 to n-1 only since no one is a friend of him - or herself, and friendship is symmetrical-if x is a friend of y then y is a friend of x.)

Now n people have friends as 0,1,2 ... n-1 such that each has distinct number of friends.

But say if A has 0 friends, it means A has no friend,

but there is one B who has n-1 friends i. e. all the others in the party are friends to him including A

This is a contradiction. So it follows in any group of people, two of them have the same number of friends in the group.