配合PPT食用口感更佳，以下所有问题标号均为PPT中的标号。

1.0 基础概念及定义

• 导出子图：由原图顶点的一个子集及连接该子集内顶点的所有边构成的子图。

• 生成子图：包含原图所有顶点的子图。

• 完全子图：一个是完全图的导出子图，又称团。

2.0 图的基本性质和基本处理方法

2.3 最小度数路径1

设图 \(G\) 的顶点的最小度数是 \(\delta\), 则 \(G\) 包含一条长为 \(\delta\) 的路径。

Proof：
取一条最长路，它的一个端点的所有邻点都在该路上，该端点的度数 \(\ge \delta\) 意味着它在路上至少有 \(\delta\) 个不同的邻点，因此该路径的长度 \(\ge \delta\)。

2.5 最小度数路径2

设图 \(G\) 的最小度数为 \(\delta\)，如果 \(G\) 中最长路径的长度为 \(\delta\)，那么 \(G\) 是多个不相交完全图 \(K_{ \delta + 1}\) 的并。

Proof：
考虑2.3中提到的最长路，不妨设其为 \(v_1v_2v_3...v_{\delta +1}\)，且 \(v_1\) 和 \(v_{\delta +1}\)的所有邻点必定都在该路径上，若存在路径中的一个点 \(v_i\) 与路径外的一个点 \(u\) 连边，则必存在路径 \(uv_iv_{i-1}...v_1v_{i+1}v_{\delta +1}\) 长度为 \(\delta +1\)，与最长路长度为 \(\delta\) 矛盾，故路径上所有点的邻点都在该路上，又因为最小度数为 \(\delta\)，所以这是一个完全图。

2.6 三元环

没有三角形的 \(n\) 个顶点的图的边数的最大值是 \(\lfloor\frac{n^2}{4}\rfloor\)。

Proof：

• 构造上界：取一个左部点数量 \(\lfloor\frac{n}{2}\rfloor\)，右部点数量 \(\lceil\frac{n}{2}\rceil\) 的完全二分图，其边数为 \(\lfloor\frac{n^2}{4}\rfloor\)。
• 证明上界：
  \[\begin{gather} d(u) + d(v) \le n \\ \sum_{(u,v) \in E} (d(u) + d(v)) \le |E|n \\ \sum_{(u,v) \in E} (d(u) + d(v)) = \sum_{u \in V} d^2(u) \ge \frac{(\sum_{u \in V}d(u))^2}{n} = \frac{4|E|^2}{n} \\ |E|n \ge \frac{4|E|^2}{n} \\ |E| \le \frac{n^2}{4} \end{gather}\]
  • (1)：不存在三元环，即不存在一个点同时与某条边的两个端点相邻。
  • (3)：均值不等式。