Skip to main content
Post Made Community Wiki
Source Link
zeb
  • 8.7k
  • 6
  • 37
  • 50

The universal friend theorem:

Suppose that in a finite graph, every pair of vertices have exactly one neighbor in common. Then the graph must a windmill, i.e. there is a hub vertex that neighbors every other vertex, and the remaining vertices are connected to each other in pairs.

Also sometimes phrased as, "in a party, every two people have a unique friend in common. Then there is a person at the party who is friends with everyone."