MathLabs

Problem 3

Let nn be a positive integer. nn people take part in a party. For each pair, either the two people are acquainted or they are not. What is the maximum possible number of pairs that are not acquainted but have a common acquaintance among the participants?
Step 1 of 6: Construction
Previous stepNext step
(n−12)=(n−1)(n−2)2\binom{n-1}{2}=\frac{(n-1)(n-2)}2
Detailed analysis

Make one person acquainted with all other n−1n-1 people and make no other acquaintance edges. Every pair among the other people is counted, giving (n−12)\binom{n-1}{2}.