小蓝书 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}\)

具体证明以后补上。

---

题解之后写