平面图欧拉公式 | Codeboy's Blog

形式陈述

设有限非空平面图 $G$ 已选定一个边只在公共端点相交的平面嵌入。记顶点数、边数、面数为 $n,m,f$ ，面是从平面删去图后剩下的连通区域，包括无界外面。若 $G$ 连通，则

n-m+f=2.

若 $G$ 有 $c$ 个连通分量，则推广为 $n-m+f=1+c$ 。这里也允许前一条目所定义的自环、平行边嵌入；这些结构会影响后续的边数估计，却不破坏欧拉公式本身。

讨论顶点可达性时，可先删除自环、把每组平行边合并为一条边，得到同顶点集的简单图；这不改变连通分量。因而这里的连通性采用上述简单图的连通性。若先在该简单图中取生成树，再为每条树边选回一条原图边，就得到保留全部顶点的树骨架；边的选择不会引入自环或平行对。

证明骨架

连通图若有圈，删去圈上的一条边；在多重图中，圈也包括自环或两条平行边组成的闭曲线。嵌入中的圈是一条简单闭曲线，Jordan 曲线定理将其两侧分开。该边不是桥，删除后图仍连通，原来相邻的两个面合并，使 $m$ 和 $f$ 各减一， $n-m+f$ 保持不变。重复直到没有圈，此时也没有自环或平行边对，所得骨架是简单图意义的生成树。由树的等价刻画，它有 $m=n-1$ ，不会围出有界区域，故 $f=1$ ，于是交替和为二。反向看，从生成树按原嵌入补回非树边，每次恰把一个面分成两个。

对不连通图，可在不同分量间补入 $c-1$ 条不相交的连接边，使图连通而不新增面。把连通公式写成 $n-(m+c-1)+f=2$ ，就得到推广式。

直觉

欧拉公式记录画图过程中哪些局部变化会彼此抵消。在线段中插入一个顶点时，顶点和边各增一；在一个面内连接已由路径相连的两点时，边和面各增一。它们改变图的细节，却不改变这个交替和。

面是嵌入带来的几何对象，但对同一张平面图，面数已经由 $n,m,c$ 决定。改变嵌入可能改变面边界及分量的嵌套方式，不能改变面数。若图画出了交叉而未把交点声明为顶点，就不能把纸上切出的区域直接代入公式。

例子与边界

三角形有 $n=3,m=3,f=2$ ；任何非空树有 $f=1$ ，包括只有一个顶点的树。立方体骨架有 $n=8,m=12,f=6$ ，得到 $8-12+6=2$ 。两个互不相交的三角形有 $n=6,m=6,c=2,f=3$ ，故交替和为三；即使把一个画在另一个里面，面数仍是三。

边数估计需要额外条件。简单连通平面图在 $n\ge3$ 时，每个面边界闭游走长度至少三，且每条边有两个侧面，所以面边界长度总和为 $2m$ ，即 $3f\le2m$ 。桥的两侧可以属于同一个面，此时这条边仍必须计两次。结合欧拉公式，

3(2-n+m)\le2m,\qquad m\le3n-6.

树的外面边界也可能反复经过顶点，因此“面”不一定是由互异顶点围成的多边形。平行边可能围出长度二的面，自环可能围出长度一的面，故上述不等式不能不加修改地用于多重图。

边数界是必要条件，不是平面性判据。 $K_5$ 有十条边，违反 $3\cdot5-6=9$ ，所以非平面； $K_{3,3}$ 却满足 $9\le3\cdot6-6=12$ 。后者没有三角形，若能平面嵌入，每个面至少四边，会进一步给出 $m\le2n-4=8$ ，才与九条边矛盾。

推论与应用

配合握手引理 $\sum_v\deg(v)=2m$ ，简单平面图的边数界说明平均度小于六，因而存在度至多五的顶点。对逐步删点得到的子图仍可使用这一事实，得到六色贪心着色的基础；降到五色还需要额外的换色论证。

把无界面补成球面上的一个面，欧拉公式便成为球面的Euler 示性数为二的具体表现。在其他曲面上，需要使用相应示性数，并注意嵌入是否构成各面都是开圆盘的胞腔分解。

参考资料

Mitchel T. Keller、William T. Trotter，Applied Combinatorics，在线版，§5.5 “Planar Graphs”，定理 5.33 及边数界；正文（访问于 2026-09-20）。
Oscar Levin，Discrete Mathematics: An Open Introduction，第3版在线版，§4.3 “Planar Graphs”，Euler 公式与非平面图；正文（访问于 2026-09-20）。

形式陈述 ​

证明骨架 ​

反向链接

形式陈述

证明骨架