Graph Theory Question: Show that, in any group of 2 or more people, there are always 2 with exactly the same number of friends inside the group. Show that, in any group of 2 or more people, there are always 2 with exactly the same number of friends inside the group.
So, intuitively, this makes perfect sense, but I am having some trouble getting it down on paper. Could someone help me get started please?
 A: You have to assume friendship is symmetric.  If there are $n$ people, there are $n$ possible numbers of friends, from $0$ through $n-1$.  If there are not two people with the same number of friends, each of these must occur once.  Consider the people who have $0$ and $n-1$ friends-are they friends?
A: We have $n$ people in group. One can have from $0$ to $n-1$ friends, if no 2 people have the same amount of friends, then degree sequence for such graph would look like this: 
$(\underbrace{0,1,2,3}_{n-1\text{ numbers}},..,n-1)$
Now, according to score theorem, we can see that this graph can't exist, $n-1$ degree vertex can't be connected with $0$ degree vertex. There have to be two people with same amount of friends.
A: According to Havel-Hakimi algorithm a degree sequence $$d=\{d_1,d_2,......,d_n\}$$ corresponds to a simple graph if and only if the list $$d'=\{d_2-1,d3-1,.....,d_{d_1+1}-1,d_{d_1+2},.....,d_n\}$$ is a sequence of non-negative integers and is graphic.
Here to prove the required statement, let all the degrees(number of friends) of all the nodes(persons) be different and the graph $G$ be simple initially; this is our assumption.Now we would try to contradict this statement.
Let the number of persons be $K$ then the degree sequence would be (in increasing order) as follows:-
$$d=\{k-1,k-2,.......,k-(k-1),0\}$$ now if we apply Havel-Hakimi algorithm,we delete the first node corresponding to $(k-1)^{th}$ degree and subtract $1$ from all the subsequent $k-1$ degrees, we see that $0$ becomes $-1$ ,which is negative so it is not a simple graph i.e. one person may be a friend two or more times to another or may be a self friend which is ridiculous and against the normal assumption in the question, 
This contradicts to our assumption that $G$ is simple, Hence proved that there must be at least two persons with exactly same number of friends.
