Problem
COM-B1-M04-P021 Many Acquaintances
#21
★★★★☆ Level 4 of 5
In a group of \(15\) people, each person knows at least \(7\) others. Prove that there are at least \(53\) acquainted pairs.
Sum degrees in the acquaintance graph.
Build the acquaintance graph. The sum of degrees is at least \(15\cdot7=105\). Each acquainted pair contributes twice to the degree sum, so the number of edges is at least \(105/2=52.5\). Since it is an integer, it is at least \(53\).
Estimate by double counting and rounding.