Exercise 1097Combinatorics › Pigeonhole principleL1Added 3 Nov 2026

The handshake lemma by pigeonhole

#pigeonhole#handshake#graph degrees

Statement

Show that in any group of $n\ge2$ people, two have the same number of friends in the group.

Hint

Each person's number of friends is between $0$ and $n-1$ . But $0$ and $n-1$ cannot both occur.

Show solutionHide solution

Solution

Degrees. Degrees are in $\{0,1,\ldots,n-1\}$ .

Impossible combination. If someone has $0$ friends, nobody has $n-1$ (which would mean being friends with everyone). So at most $n-1$ distinct degrees occur among $n$ people.

Pigeonhole. Two people share the same degree.

Conclusion. Two people have the same number of friends.

The handshake lemma by pigeonhole

Statement

Solution

More problems in Pigeonhole principle