0

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.)

*This question is from the textbook Essential discrete mathematics for computer science by Harry R. Lewis.

The problem intuitively makes sense to me but I'm not able to formulate a mathematical proof.

Bill Dubuque
  • 272,048
Abhinav Gupta
  • 1

1 Answers1

0

Hint: suppose there are $n$ people in the group. What are the possible numbers of friends someone can have? Is it possible for all of these to occur simultaneously?

Especially Lime
  • 40,828