问题描述
题意：已知有一个 \(n\) 点的无向图 \(G\) 不包含三元环，求 \(G\) 边数的最大值。
提示：设 \(G=(V,E)\) 是一个无向图。我们称 \(G\) 包含三元环是指存在三个点 \(a,b,c\) 满足 \(\{(a,b),(b,c),(a,c)\}\subseteq E\)。
例如当 \(n=5\) 时，下面是一个不包含三元环的图的例子，
该图包含 \(5\) 个点和 \(6\) 条边，可以证明所有没有三元环的 \(5\) 个点的无向图的边数均不超过 \(6\)。
解答
设 \(G=(V,E)\) 是某个无向图，包含 \(n\) 个点 \(m\) 条边。点 \(v\) 的度数是指连接点 \(v\) 的边的数量，记作 \(\mathrm d(v)\)。于是有
\[\sum_{x\in V}\mathrm d(x)=2m \]以及
\[\begin{aligned}\sum_{x\in V}\mathrm d^2(x)&=\sum_{x\in V}\sum_{(x,y)\in E}\mathrm d(x)\\&=\sum_{(x,y)\in E}\mathrm d(x)+\mathrm d(y)\end{aligned} \]现在假设 \(G\) 不包含三元环。若 \((x,y)\) 是图 \(G\) 的边，那么对于任意一个点 \(v\)，一定有 \((x,v)\not\in E\) 或 \((y,v)\not\in E\)，这说明
\[\mathrm d(x)+\mathrm d(y)\leq n \]于是
\[\sum_{(x,y)\in E}\mathrm d(x)+\mathrm d(y)\leq nm \]另一方面，根据柯西-施瓦茨不等式得到
\[\sum_{x\in V}\mathrm d^2(x)\geq\frac 1n\left(\sum_{x\in V}\mathrm d(x)\right)^2=\frac{4m^2}{n} \]联立上述结果，得到
\[nm\leq \sum_{(x,y)\in E}\mathrm d(x)+\mathrm d(y)=\sum_{x\in V}\mathrm d^2(x)\leq\frac{4m^2}{n} \]整理得到 \(m\leq n^2/4\)，这说明 \(m\) 的不超过 \(\lfloor n^2/4\rfloor\)，这个上界可以由完全二分图 \(\mathrm K(\lfloor n/2\rfloor,\lceil n/2\rceil)\) 取到。
2022年12月16日 与东莞松山湖
标签：包含,组合,sum,选讲,个点,leq,三元,杂题,mathrm From： https://www.cnblogs.com/szdytom/p/combinatorial-misc-4.html