Two people with the same number of friends

Idea. Count the possible values and show that there are really only $n-1$ of them.

Values. Each person has between $0$ and $n-1$ friends. Suppose some person $A$ has $0$ friends and some person $B$ has $n-1$ friends. Then $B$ is a friend of everybody, in particular of $A$, so $A$ has at least one friend: contradiction. Hence the values $0$ and $n-1$ do not occur together.

Pigeonhole.
- If nobody has $0$ friends, all the numbers of friends lie in $\{1,\dots,n-1\}$.
- If somebody has $0$ friends, then nobody has $n-1$ friends, and all the numbers lie in $\{0,\dots,n-2\}$.

In both cases the $n$ people take at most $n-1$ different values, so two people have the same number of friends.

Remark. The statement is false if we allow a person to be their own friend or friendships to be one-way. The mutuality is used exactly once, in the key step.

Lesson. Pigeonhole: count the boxes carefully, and look for a hidden constraint that removes one box.