Problem
COM-B1-M12-P016 Set 4. Acquaintances
#16
★★★☆☆ Level 3 of 5
Prove that in a group of \(10\) people, two have the same number of acquaintances.
Values \(0\) and \(9\) cannot occur together.
Possible acquaintance numbers are from \(0\) to \(9\), but \(0\) and \(9\) are incompatible. Thus there are at most \(9\) different values for \(10\) people. By pigeonhole, two degrees are equal.
Graph plus pigeonhole.