Skip to content
Quantoros

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

Related questions