设是阶数
的简单平面图。证明：
证：
一、证明准备
1.欧拉公式:对于任意简单平面图，有
。其中
是顶点数，
是边数，
是面数。
2.顶点度数与边数的关系:对于图,所有顶点的度数之和是边数的两倍，即
。
3.每个面的度数性质:在平面图中，每个面的边界至少是三条边，设表示第
个面的边界边数，那么每个面的度数至少是3，即
。
二、关键推导
1.利用二次图论不等式:
我们利用已知的一个关于平面图的结果:对于一个阶数为的简单平面图
，有$$
\sum_{x \in V} d_G(x)^2\leq 4e$$
其中，因此有
。
2.目标不等式的化简:我们需要证明:
$$
\sum_{x \in V} d_G(x)^2 \leq 2(v+ 3)^2-62
$$
展开右边的表达式:
$$
2(v + 3)^2 - 62 = 2(v2+6v+9)-62=2v2+12v+18-62=2v^2+12v-44
$$
3.比较大小:我们需要证明:
$$
12v - 24\leq 2v^2+12v-44
$$
移项得到:
$$
0 \leq 2v^2-20
$$
化简为:
$$
v^2\geq 10
$$
对于，显然
，因此不等式成立。
综上所述，我们证明了对于阶数的简单平面图
，有
$$
\sum_{x \in V} d_G(x)^2 \leq 2(v+3)^2-62
$$
这个不等式在 时恒成立。
网友评论