$S$ 为 $m$ 个正整数对 $(a,b)$ $(1\leqslant a,b\leqslant n,a\not=b)$ 所组成的集合（$(a,b)$ 与 $(b,a)$ 被认为是相同的）．证明：至少有 $\dfrac{4m}{3n}(m-\dfrac{n^2}{4})$ 个三元数组 $(a,b,c)$，适合：$(a,b),(a,c)$ 及 $(b,c)$ 都属于 $S$．
【难度】
【出处】
无
【标注】
【答案】
略
【解析】
做一个图 $G$：用点 $v_i$ 表示数 $i$，$i=1,2,\cdots,n$．当且仅当 $(i,j)\in S$ 时，点 $v_i$ 与点 $v_j$ 相邻．于是图 $G$ 有 $n$ 个顶点，$m$ 条边．要证明的问题就是：$G$ 中至少有 $\dfrac{4m}{3n}(m-\dfrac{n^2}{4})$ 个三角形．
令顶点 $v_i$ 的度为 $d_i$，$G$ 中边的集合为 $E$，设 $(v_i,v_j)\in E$，则它的两个端点 $v_i,v_j$ 向其余 $n-2$ 个顶点共引出 $d_i+d_j-2$ 条边，故至少有 $d_i+d_j-n$ 对分别由 $v_i,v_j$ 引向同一顶点的边，它们与边 $(v_i,v_j)$ 构成三角形，因此 $G$ 中至少有 $d_i+d_j-n$ 个三角形包含边 $(v_i,v_j)$．又因为 $G$ 中每个三角形被计算了三次，故 $G$ 中至少有 $k=\dfrac{1}{3}\sum_{(v_i,v_j)\in E}(d_i+d_j-n)$ 个三角形．由于顶点 $v_i$ 的度 $d_i$ 的上述和式中出现 $d_i$ 次，边的条数为 $m$，故 $k=\dfrac{1}{3}(\sum_{i=1}^n d_i^{2}-mn)$．
因为 $\sum_{i=1}^{n}d_i=2m$，由柯西不等式，得 $k\geqslant \dfrac{1}{3}[\dfrac{1}{n}(\sum_{i=1}^n d_i-mn)]$
$=\dfrac{1}{3}(\dfrac{4m^2}{n}-mn)$
$=\dfrac{4m}{3n}(m-\dfrac{n^2}{4})$．
令顶点 $v_i$ 的度为 $d_i$，$G$ 中边的集合为 $E$，设 $(v_i,v_j)\in E$，则它的两个端点 $v_i,v_j$ 向其余 $n-2$ 个顶点共引出 $d_i+d_j-2$ 条边，故至少有 $d_i+d_j-n$ 对分别由 $v_i,v_j$ 引向同一顶点的边，它们与边 $(v_i,v_j)$ 构成三角形，因此 $G$ 中至少有 $d_i+d_j-n$ 个三角形包含边 $(v_i,v_j)$．又因为 $G$ 中每个三角形被计算了三次，故 $G$ 中至少有 $k=\dfrac{1}{3}\sum_{(v_i,v_j)\in E}(d_i+d_j-n)$ 个三角形．由于顶点 $v_i$ 的度 $d_i$ 的上述和式中出现 $d_i$ 次，边的条数为 $m$，故 $k=\dfrac{1}{3}(\sum_{i=1}^n d_i^{2}-mn)$．
因为 $\sum_{i=1}^{n}d_i=2m$，由柯西不等式，得 $k\geqslant \dfrac{1}{3}[\dfrac{1}{n}(\sum_{i=1}^n d_i-mn)]$
$=\dfrac{1}{3}(\dfrac{4m^2}{n}-mn)$
$=\dfrac{4m}{3n}(m-\dfrac{n^2}{4})$．
答案
解析
备注
