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