平面图与欧拉公式

若无向图能画在平面上，使边只在共同端点相遇、途中互不交叉，就称它为平面图。判断时允许弯曲或重新安排顶点；某一幅画有交叉，不等于图本身不是平面图。一次无交叉画法叫平面嵌入，它把平面分成若干面，图外无界的区域也算一个面。

用边界数清点面

只画一个三角形，三个顶点、三条边、两个面：内部一个，外部一个。添一条从某顶点通往三角形外新顶点的“树枝”，得到四顶点、四边、仍为两个面；树枝没有围出新区。若在三角形内部添一点，并把它分别连向三个角，就得到四顶点、六条边、四个面：内部被分成三个三角形，加上外部一面。下图把三个内部面标作 $F_{1}, F_{2}, F_{3}$ ，外部虽向四周无限延伸，仍只计作 $F_{4}$ 。两例都符合 $v - e + f = 2.$

三角形abc内部一点d连接三个顶点，形成三个内部三角面F1至F3，外部区域标F4 — 图中 v=4、e=6、f=4，外部的 F4 也须计入，故 4−6+4=2。

欧拉公式断言：有限、连通的平面图无论采用哪种平面嵌入，顶点数 $v$ 、边数 $e$ 与面数 $f$ 总满足上述等式。证明可从连通图中取一棵生成树。它含全部 $v$ 个顶点和 $v - 1$ 条边，平面上只有外部一个面，因此 $v - (v - 1) + 1 = 2$ 。再把原图其余的边一条条补回：每条新增边两端在已有树中已连通，因而与已有路径合成一个环；在无交叉嵌入中，它把原来一个面分成两个面。每次 $e$ 和 $f$ 同增 1， $v - e + f$ 不变，证明完成。连通条件不能漏：两个相互分离的单点有 $v = 2, e = 0, f = 1$ ，结果为 3。

用欧拉公式判断不可画性

现在继续假设图有限、连通、简单、平面且 $v \geq 3$ 。每个面的边界沿边走一圈至少走三步；即使某条边是桥，它在同一个面的边界上也会被来回经过两次。把所有面的边界行走长度相加，每条边恰计两次，因此 $3 f \leq 2 e$ 。与 $v - e + f = 2$ 合起来，先代入 $f = 2 - v + e$ ，再整理 $3 (2 - v + e) \leq 2 e$ ，得到 $e \leq 3 v - 6$ 。完全图 $K_{5}$ 有 $v = 5, e = 10$ ，却要求 $e \leq 9$ ，因此不可能画成平面图。这个证明用的是必要条件；某图满足 $e \leq 3 v - 6$ ，也未必就是平面图。

在相同的有限连通简单平面图前提下，若图还是二分图，就没有三角形；每个面的边界行走长度至少为 4，可得 $4 f \leq 2 e$ 与 $e \leq 2 v - 4$ 。对 $K_{3, 3}$ ， $v = 6, e = 9$ ，而上界为 8，所以它同样不是平面图。这里的两种不等式把“线总会打结”的图像直觉变成可以核算的证明。

练习时可先数图中一条“树枝”究竟添了多少个面：答案是零，因为它只在原来同一个面内伸出再沿自身返回，边界计数却多走两步。若原图有 $c$ 个连通分量，可在不相交嵌入中加 $c - 1$ 条跨分量的桥使其连通；桥不添面，故一般公式变为 $v - e + f = 1 + c$ 。例如两个孤立点有 $2 - 0 + 1 = 3 = 1 + 2$ 。这也解释了推导 $e \leq 3 v - 6$ 时不能把“连通”假设省去。

作为另一个可手算的嵌入，取四边形并在内部添一条对角线：此时 $v = 4, e = 5$ ，内部被分成两个三角面，再加外面共 $f = 3$ ，于是 $4 - 5 + 3 = 2$ 。若去掉对角线，边数与面数各减 1，等式仍成立。这与前面“给树添一条成环边就新增一个面”的证明是同一件事的具体演示；不必把每种画法都当成一个需要重新记忆的公式。

参考资料