More on Numbers of Friends:
Prove that in any group of people (no matter how large), there are always two people with exactly the same number of friends within the group. Note that we define friendship to be symmetric, so that if A is friends with B, then B is also friends with A.
UPDATE: Assume the group has at least two people.
Proof by contradiction. For there not to be two people with the same number of friends then each person must have a different number of friends. In a group of N people the distribution of 0 to N-1 friends must be among the N people. The Nth person has N-1 friends (all those before him), however the N-1 person has N-2 friends (all those before him) plus the Nth person because the friendship is bidirectional, remember the Nth person is friends with the N-1. Thus, the N-1 person also has N-1 friends. So the number of friends is not unique among the N.
This is a basic binomial distribution.
QED.
First, just consider the case where no one is allowed to be a stranger, i.e. the graph is connected.
There are n vertices. Each vertex must have at least one edge incident on it. The degree of a vertex is the number of edges incident on that vertex. There are only n-1 distinct values that a vertex can have for its degree (1, 2, ... n-1.) But there are n vertices, so the nth vertex must have a degree that collides with an already used value.
If you allow strangers, then you limit the size of the highest allowed degree. If you allow two strangers (or more), then you're done. If you allow one, then the connected graph shrinks by one, so the numbers for vertices go from 0 to n-2, and the same argument applies.
His proof is that you can't have an N-1 friendster and a zero friendster in the same group. This obviously works.
Your proof is that you can't have an N-1 friendster and an N-2 friendster in the same group... not so obvious.
You wrote:
"however the N-1 person has N-2 friends (all those before him) plus the Nth person because the friendship is bidirectional"
Who says the N-2 person must be friends with all of those before him AND the N-1 person?
Let's say person A is friends with BCDEF, and person B is friends with ACDE.
That's an example of a six-person group in which an N-1 and an N-2 coexist legally.
1. For any group of N people, each person has a number of friends (F).
2. There can be at most N-1 different values for F because no person can be a friend with himself.
3. Thus, if there are N instances of F, with only N-1 different values, then there must be at least two instances of F with the same value.
Adam’s “proof” is intuitively correct, just not formally. That was my only complaint. The problem asked for a proof. He didn’t state that the only way any two people from a group of N people cannot have the same number of friends is that everyone must have a different number of friends, and that this proves by contradiction at least two must have the same number of friends. Adam correctly demonstrates the contradiction that one person cannot have zero friends while another has N-1 friends.
I demonstrate from the other “end” showing that at least two people must have the same number of friends. You are troubled by the assumption of the linear selection of people. Just select the N people randomly from the group and assign them into the groups of friends. It is really just a re-labeling. The same complaint you make against me you can make against him – why should the first person be assigned zero friends, why not the tenth? It doesn’t matter. That was not my complaint against Adam’s proof. He is correct in “getting it”, I just thought it wasn’t stated explicitly as a contradiction and thus not formally. Yes he stated implicitly, and yes he got it first. I only thought to make it a bit more rigorous.