Exercise 1626Combinatorics › Counting principlesOlympiadAdded 3 Nov 2026

Pigeonhole in a graph

#pigeonhole#graph#vertex degree

Statement

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

Hint

Each person can have $0$ to $n-1$ friends, but $0$ and $n-1$ cannot both occur.

Show solutionHide solution

Solution

Degrees. Each degree is in $\{0,\ldots,n-1\}$ . But $0$ (no friends) and $n-1$ (everyone else) cannot both occur: if one person has $n-1$ friends, everyone else has $\ge1$ ; if someone has $0$ friends, no one has $n-1$ .

Pigeonhole. So there are at most $n-1$ possible degree values for $n$ people: two have the same degree.

Conclusion. Two people have the same number of friends.

Pigeonhole in a graph

Statement

Solution

More problems in Counting principles