At any party, prove two people always know the exact same number of others
At a party of any size, some guests shake hands with some others and not with the rest. Prove that no matter how the handshakes happen to fall, there must always be at least two people at the party who shook hands with exactly the same number of other guests.
Reveal the answer
In a party of n people, each person shakes between 0 and n-1 hands — but 0 and n-1 can't both occur, since the person who shook everyone's hand rules out anyone shaking zero hands. That leaves only n-1 possible handshake counts to share among n people, so by the pigeonhole principle at least two people must match. This is a classic application of the handshaking lemma from graph theory, where 'people' are vertices and 'handshakes' are edges.
— Leonhard Euler, Handshaking lemma — Degree sum formula in graph theory