The Friendship Theorem
Image: Wikimedia Commons

If every pair of people in a group have exactly one friend in common, then there’s always one person who is a friend to everyone.

This rather heartwarming fact was proven by Paul Erdős, Alfréd Rényi, and Vera T. Sós in 1966. It’s sometimes more cynically known as the paradox of the politician.

The Erdős proof uses combinatorics and linear algebra, but in 1972 Judith Longyear published a proof using elementary graph theory.

See The Elevator Problem.