Skip to main content
1 of 1
Post Made Community Wiki
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."

zeb
  • 8.7k
  • 6
  • 37
  • 50