1. Mantel 定理: 禁止三角形

我们从以下基本问题开始讨论极值图论.

问题 1.1. $n$ 顶点的无三角形 (triangle-free) 图中, 最多有多少条边?

注意二分图总是无三角形的, 而一个完全二分图最多有 $\lfloor n^2/4\rfloor$ 条边 (这个完全二分图两侧的点数相同或至多相差一个点) . Mantel 定理指出, 无三角形的图不能有比这更多的边.

定理 1.2 (Mantel 1907). 任意 $n$ 顶点的无三角形图最多有 $\lfloor n^2/4\rfloor$ 条边.

我们将给出定理 1.2 的两个不同版本的证明.

版本 1. 令 $G=(V,E)$ 表示一个具有 $n$ 个顶点和 $m$ 条边的无三角形图. 观察到如果两个点 $x,y\in V$ 之间有边 $xy\in E$, 那么 $x$ 和 $y$ 不能和同一个点相邻. 因此, $d(x)+d(y)\le n$, 这意味着$$\sum _{x\in V}d(x{)}^2=\sum _{xy\in E}(d(x)+d(y))\le mn$$

第一个等号成立是因为每个顶点对等式右边的贡献也是该顶点度数的平方. 另一方面, 根据握手引理 ¹, ${\sum }_{x\in V}d(x)=2m$. 根据 Cauchy-Schwarz 不等式和上面的方程可以得到$$4m^2={\left(\sum _{x\in V}d(x)\right)}^2\le n\left(\sum _{x\in V}d(x{)}^2\right)\le m{n}^2$$因此 $m\le n^2/4$. 由于 $m$ 是一个整数, 所以我们有 $m\le \lfloor n^2/4\rfloor$.

$\square$

版本 2. 令 $G=(V,E)$ 和上面一样. 由于 $G$ 无三角形, 所以每个顶点 $x\in V$ 的所有邻点 $N(x)$ 是一个独立集 ².

令 $A\subseteq V$ 是最大独立集, 那么对所有 $x\in V$, 我们有 $d(x)\le |A|$ . 令 $B=V\backslash A$. 由于 $A$ 的顶点之间无连边, $G$ 的每条边都与 $B$ 中的顶点相连, 所以, $$\begin{array}{rl}e(G)& \le \sum _{x\in B}d(x)\le |A||B|\\ & {\le }_{\text{AM-GM}}\left[{\left(\frac{|A|+|B|}{2}\right)}^2\right]=\lfloor \frac{n^2}{4}\rfloor \end{array}$$

$\square$

笔记 1.3. 为了使 Mantel 定理中的等号成立, 在上面的证明中, 我们必须有

•	$e(G)={\sum }_{x\in B}d(x)$, 这意味着没有两端点都在 $B$ 中的边.
•	${\sum }_{x\in B}d(x)=|A||B|$, 这 (与上一条一起) 意味着 $B$ 中的每个顶点与都与 A 中所有顶点相连.
•	AM-GM 中的相等情况必须成立 (或几乎成立, 也就是当 $n$ 为奇数时的情况) , 因此 $||A|-|B||\le 1$.

因此, $n$ 顶点的无三角形图恰好具有 $\lfloor n^2/4\rfloor$ 条边当且仅当它是完全二分图 $K_{\lfloor n/2\rfloor ,\lceil n/2\rceil }$.