自动搬运

查看原文

来自洛谷，原作者为

	WYXkk Zzz Zzz

搬运于2025-08-24 22:19:09，当前版本为作者最后更新于2020-04-02 14:55:54，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

---

由 图兰定理（Turán's theorem） 可知，本题答案为 $\left\lfloor\dfrac{n^2}4\right\rfloor$。

$\texttt{code(python):}$

n=int(input())
print(n*n//4)

图兰定理：假如一个 $n$ 个点的简单图中任意 $3$ 个点都不互相连接，则其边数不超过 $\left\lfloor\dfrac{n^2}4\right\rfloor$。

图兰定理的证明：

取一个符合条件的图。记 $d(X)$ 为与 $X$ 相连的边的数量，称为 $X$ 的度数。

假设所有 $n$ 个点中，$A$ 的度数最大，为 $k$，$B_1,B_2,\cdots,B_k$ 与 $A$ 相连，$C_1,C_2,\cdots,C_{n-k-1}$ 与 $A$ 不相连。

由于 $A$ 与 $B_1,B_2,\cdots,B_k$ 都有连边，假如存在 $B_iB_j$ 这条边，那么 $AB_iB_j$ 三个点互相连接，矛盾。因此 $B_i$ 之间没有连边，故 $d(B_i)\le n-k$（至多与所有 $C_j$ 和 $A$ 连边）。

同时，由于 $d(A)$ 最大，为 $k$，故 $d(C_j)\le k$。

因此，设边数为 $e$，则

$$\begin{aligned}e&=\dfrac{\sum d(X)}2\\&=\dfrac{d(A)+\sum\limits_{i=1}^kd(B_i)+\sum\limits_{j=1}^{n-k-1}d(C_j)}2\\&\le\dfrac{k+k\times(n-k)+(n-k-1)\times k}2\\&=k\times(n-k)\\&\le\left\lfloor\dfrac{n^2}4\right\rfloor\end{aligned} $$

记 $k=\left\lfloor\dfrac n2\right\rfloor$，则当且仅当图为 $K_{k,n-k}$，即两边点数分别为 $k$ 和 $n-k$ 的完全二分图时取到等号。