At a party of 20 people, friendship is mutual and nobody is their own friend. Prove two people have equal numbers of…
Quant ResearchLevel: IntermediateGraph pigeonhole
At a party of 20 people, friendship is mutual and nobody is their own friend. Prove two people have equal numbers of friends there.
Hints
- Why do the apparently 20 possible counts not all coexist?
- Apply pigeonhole after removing the incompatible extremes.
Answer
Degrees lie in 0,...,19, but 0 and 19 cannot both occur: a person knowing everyone cannot coexist with someone knowing nobody. Therefore only 19 degree values can be used by 20 people, forcing a repeat.
Source and licence: Oscar Levin — Discrete Mathematics: An Open Introduction, 3rd edition · CC-BY-SA-4.0 · answer: Quantoros editorial