Turán定理的无三角形情形(Mantel定理)

对 $n$ 归纳。当 $n \le 2$ 时命题显然成立,因为 $\lfloor n^2/4 \rfloor \ge 0$ 且至多2个顶点的图至多有1条边。

假设命题对所有顶点数小于 $n$ 的无三角形图成立,设 $G$ 是 $n$ 个顶点上的无三角形图。若 $G$ 没有边则界显然成立,故设 $G$ 有一条边 $uv$。由于 $G$ 无三角形,$u$ 与 $v$ 没有公共邻居,即 $N(u) \cap N(v) = \varnothing$。

因为 $N(u)$ 与 $N(v)$ 是 $n$ 个顶点集合中的不相交子集,故 $\deg(u)+\deg(v) = |N(u)|+|N(v)| = |N(u) \cup N(v)| \le n$。

从 $G$ 中删去 $u$ 与 $v$,得到 $n-2$ 个顶点上的无三角形图 $G'$。$G$ 的每条边要么是边 $uv$,要么是 $u$ 或 $v$ 到其余顶点的边,要么是 $G'$ 的边;仔细计数可得 $e(G) = e(G') + \deg(u) + \deg(v) - 1$(其中 $-1$ 修正了边 $uv$ 在 $\deg(u)+\deg(v)$ 中被计入一次但它并非 $G'$ 的边这一点)。

由归纳假设 $e(G') \le \lfloor (n-2)^2/4 \rfloor$,故 $e(G) \le \lfloor (n-2)^2/4 \rfloor + n - 1$。直接计算得 $(n-2)^2/4 + n - 1 = n^2/4 - n + 1 + n - 1 = n^2/4$,分别检验 $n$ 的奇偶情形可知 $\lfloor (n-2)^2/4 \rfloor + n - 1 \le \lfloor n^2/4 \rfloor$ 恰好成立。因此 $e(G) \le \lfloor n^2/4 \rfloor$,归纳完成。

对于极值情形,两部大小为 $\lfloor n/2 \rfloor$ 与 $\lceil n/2 \rceil$ 的完全二部图不含三角形(任何三角形都需要同一部分内的一条边,但不存在这样的边),且恰好有 $\lfloor n/2 \rfloor \cdot \lceil n/2 \rceil = \lfloor n^2/4 \rfloor$ 条边,因此该界是紧的。