小蓝书 17.3

$k$ 部图：

若图 $G=(V,E)$ 的点集 $V$ 可以被分解为 $k$ 个两两不交非空子集的并，并且没有任何一条边的两个端点都在同一个子集中，则称 $G$ 为 $k$ 部图 ，记作 $G = (V_1,V_2,\cdots,V_k;E)$ 。

完全 $k$ 部图：

若 $k$ 部图 $G = (V_1,V_2,\cdots,V_k;E)$ 中，任何两点 $u \in V_i,v \in V_j, i \ne j$ 均有 $(i,j) \in E$ ，则称 $G$ 为完全 $k$ 部图

图的直径：

记 $d(u,v)$ 表示 $u$ 到 $v$ 的一条最短路径的长，则图的直径为 $\max_{u\ne v} d(u,v)$ 。

托兰定理：

若 $G$ 是一个有 $n$ 个顶点的图，且完全图 $K_{r+1}$ 不是 $G$ 的子图，则 $G$ 最多有 $\frac{r-1}{r}\cdot \frac{n^2}{2} = \left(1-\frac{1}{r}\right) \cdot \frac{n^2}{2}$ 条边。

此外，若 $G$ 恰好有 $\left(1-\frac{1}{r}\right) \cdot \frac{n^2}{2}$ 条边，则 $G$ 一定为托兰图 $T_{n,r}$ 。

---

小蓝书并没有立刻讲完整的托兰定理，而是首先在定理一提到了 $r=2$ 的情况，即

• 有 $n$ 个顶点且不含三角形的图 $G$ 的最大边数为 $\left\lfloor\frac{n^2}{4}\right\rfloor$ 。

接着定理二给出了托兰定理的准确定义

• 设 $n$ 阶图 $G$ 不含 $K_{m+1}$ ，则 $G$ 的边数 $e(G) \le e_m(n)$ ；当且仅当 $G$ 与 $T_m(n)$ 同构时等号成立

定理三可以利用托兰定理证明

• 设 $S = \{x_1,x_2,\cdots,x_n\}$ 是平面上直径为 $1$ 的点集，则距离大于 $\frac{\sqrt{2}}{2}$ 的点对的最大可能数目是 $\left\lfloor\frac{n^2}{3}\right\rfloor$

  并且对每个 $n$ ，存在直径为 $1$ 的一个点集 $\{x_1,x_2,\cdots,x_n\}$ ，它恰好有 $\left\lfloor\frac{n^2}{3}\right\rfloor$ 个点对，其距离大于 $\frac{\sqrt{2}}{2}$

具体证明以后补上。

---

题解之后写