一、定理陈述#
Mantel定理：对于一个具有 n 个顶点的简单无向图 G，其边数 m 满足 m≤4n2，当且仅当图 G 是一个完全二部图 K⌊2n⌋,⌈2n⌉ 时等号成立。
二、证明过程#
（一）基本设定和握手引理的应用#
- 设 xy 是图 G 的一条边，其中 d(x) 和 d(y) 分别表示顶点 x 和 y 的度数，n 是图 G 的顶点数。对于任意边 xy，有 d(x)+d(y)≤n。
- 根据握手引理，对于图 G 的顶点集 V 和边集 E，有 ∑x∈Vd(x)=2m，其中 m 是图 G 的边数。
（二）对度数平方和的分析#
- 我们得到 ∑x∈Vd(x)2=∑xy∈E(d(x)+d(y))≤mn。
- 这里等号成立的原因是：在计算 ∑xy∈E(d(x)+d(y)) 时，因为每条边 xy 对 d(x) 和 d(y) 都有贡献，所以每条边被算了两次。具体来说，对于每条边 xy∈E，在求和过程中，d(x) 由于对应顶点 x 出现一次，d(y) 由于对应顶点 y 出现一次，所以 ∑xy∈E(d(x)+d(y)) 实际上就是对每条边算了两次。
（三）应用柯西 - 施瓦茨不等式#
- 根据柯西 - 施瓦茨不等式：(∑x∈Vaxbx)2≤(∑x∈Vax2)(∑x∈Vbx2)。
- 在当前情况下，设 ax=1，bx=d(x)，则有：
- (∑x∈Vd(x))2≤n∑x∈Vd(x)2。
- 已知 ∑x∈Vd(x)=2m，将其代入上式得到 (2m)2≤n∑x∈Vd(x)2。
- 又因为 ∑x∈Vd(x)2≤mn，所以可得 4m2≤n⋅mn，即 4m2≤mn2。
（四）得出结论#
- 由 4m2≤mn2，两边同时除以 4n，得到 m≤4n2。
- 当 m=4n2 时，上述不等式都变成等式。这意味着所有顶点的度数相差不超过 1，此时图 G 是一个完全二部图 K⌊2n⌋,⌈2n⌉。
三、总结#
通过上述步骤，我们利用边和顶点度数的关系，结合握手引理和柯西 - 施瓦茨不等式，成功地证明了图 G 的边数上界为 4n2，并且明确了在边数达到此上界时图的结构特征。这种证明方法体现了图论中不同定理和不等式在推导图的性质方面的强大作用。
