MathLabs

第3题

nn 为正整数。nn 个人参加聚会，每一对人要么相识要么不相识。求不相识但在参加者中有共同熟人的点对数的最大值。
第 4/6 步：连通图上界
上一步下一步
e(G)≥n−1e(G)\ge n-1
详细分析

每个含有 nn 个顶点的连通图至少有 n−1n-1 条边.