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 5 of 6: Upper bound
Previous stepNext step
#counted pairs≤(n2)−(n−1)\#\text{counted pairs}\le\binom n2-(n-1)
Detailed analysis

Every counted pair is a nonedge. Since at least n−1n-1 pairs are edges, the number of counted pairs is at most (n2)−(n−1)=(n−12)\binom n2-(n-1)=\binom{n-1}{2}.