MathLabs

第4题

设 SS 是由 mm 个满足 1≤a<b≤n1\le a<b\le n 的正整数对 (a,b)(a,b) 组成的集合。证明存在至少 m(4m−n2)3n\dfrac{m(4m-n^2)}{3n} 个三元组 (a,b,c)(a,b,c)，使得 (a,b),(a,c)(a,b),(a,c) 和 (b,c)(b,c) 都属于 SS。
第 1/5 步：建立图的度数
上一步下一步
Di={j:(i,j)∈S or (j,i)∈S},di=∣Di∣D_i=\{j:(i,j)\in S\text{ or }(j,i)\in S\},\qquad d_i=|D_i|
详细分析

把 1,…,n1,\ldots,n 看作顶点，把 SS 中的数对看作边。令顶点 ii 的邻点集为 DiD_i，di=∣Di∣d_i=|D_i|。每条边有两个端点，故 ∑i=1ndi=2m\sum_{i=1}^n d_i=2m。