证明简单平面图中顶点度数平方和的上界

2024-11-02 本文已影响0人久别重逢已经那边v发

设 $G=(V,E)$ 是阶数 $v\geq 4$ 的简单平面图。证明： $\sum_{x\in V}d_G(x)^2≤2(v+3)^2−62$

证：

一、证明准备

1.欧拉公式:对于任意简单平面图 $G$ ，有 $v-e+f=2$ 。其中 $v$ 是顶点数， $e$ 是边数， $f$ 是面数。

2.顶点度数与边数的关系:对于图 $G$ ,所有顶点的度数之和是边数的两倍，即 $\sum_{x \in V} d_G(x) =2e$ 。

3.每个面的度数性质:在平面图中，每个面的边界至少是三条边，设 $f_i$ 表示第 $i$ 个面的边界边数，那么每个面的度数至少是3，即 $f_i\geq 3$ 。

二、关键推导

1.利用二次图论不等式:

我们利用已知的一个关于平面图的结果:对于一个阶数为 $v$ 的简单平面图 $G$ ，有$$

\sum_{x \in V} d_G(x)^2\leq 4e$$

其中 $e \leq 3v-6$ ，因此有 $\sum_{x \in V} d_G(x)^2 \leq 4(3v-6)=12v-24$ 。

2.目标不等式的化简:我们需要证明:

\sum_{x \in V} d_G(x)^2 \leq 2(v+ 3)^2-62

展开右边的表达式:

2(v + 3)^2 - 62 = 2(v^{2+6v+9)-62=2v}2+12v+18-62=2v^2+12v-44

3.比较大小:我们需要证明:

12v - 24\leq 2v^2+12v-44

移项得到:

0 \leq 2v^2-20

化简为:

v^2\geq 10

对于 $v\geq4$ ，显然 $v^2\geq16\geq 10$ ，因此不等式成立。

综上所述，我们证明了对于阶数 $v\geq 4$ 的简单平面图 $G$ ，有

\sum_{x \in V} d_G(x)^2 \leq 2(v+3)^2-62

这个不等式在 $v\geq 4$ 时恒成立。