MathLabs

第3题

nn 为正整数。nn 个人参加聚会，每一对人要么相识要么不相识。求不相识但在参加者中有共同熟人的点对数的最大值。
第 6/6 步：本步骤的论证
上一步下一步
(n−1)(n−2)/2\boxed{(n-1)(n-2)/2}
详细分析

星形构造达到上界，因此最大值是 (n−1)(n−2)/2(n-1)(n-2)/2.