Graph theory, number of friends

Question

Today our teacher gave us a math problem she wasn't sure could be solved, which is: "Andy has 25 classmates, everyone in the class has a different number of friends. How many friends does Andy have? Answer with all possible answers.

Answer 1

See what are the possible number of friends a particular person can have?

He can be friends with $0,1,2,3,4,5\dots 24$ people (as class strength $=25$). Note that the number of friends of a person has $25$ possibilities.

So if all of the $25$ people have distinct friends then some guy in the class must have $24$ friends and some guy in the class must be friend with no person, which is not possible because he must be friend with the guy with $24$ friends if you are considering mutual friendship, else this problem has an affirmative answer.

Answer 2

If you model this with a graph with each vertex representing a student and an edge between two vertices indicating a friendship between two people, then the fact that each friend has a different number of friends implies that the degree of each vertex of our graph would be distinct. This means our graph would be irregular, which is impossible, as it is well-known no simple graph can be irregular.

Answer 3

If friendship is mutual, and if the friends are only classmates, then it is impossible for everyone to have a different number of friends: in every connected subgraph (vertices are the people in the class, edges is mutual friendship), there must always be two vertices with the same degree, since there would be $n$ vertices but the possible degrees can only range from $1$ to $n-1$

So, maybe his was a trick question (within the context of a lecture on graph theory) and maybe this has nothing to do with graph theory at all, as maybe everyone in the class can have friends outside the class (which is of course a very reasonable assumption!) Indeed, now the answer is of course that Andy can have any number of friends, from 0 to the number of people in the world.

Answer 4

This seems to be a trick question.

Assume:

1. Students can't be friends with themselves.
2. Students can't have negative friends (whatever that may be interpreted as).
3. We do allow a student to have 0 friends.
4. Students are either friends or not (no fractional friendships allowed).

From the above, we know that for $N$ students, the maximum number of friends is $N-1$ ( a student is friends with every other student). So all other students must have less than $N-1$ friends.

Let's try a small class of 3 students.

Student 3 has 2 friends.

Student 2 has 1 friend.

Student 1 has 0 friends. (!)

However, if Student 1 has 0 friends, then Student 3 can't be friends with every other student, and thus there's a contradiction.

In fact, this will hold for any number of students N. (Imagine adding a student 4 with 3 friends to this list, it doesn't fix the contradiction).