平面图的欧拉公式

归纳基础。若 $E$ $= 0$ 且图连通,则它必定只由单个顶点组成($V=1$),且恰好有一个面,即整个无界平面($F=1$)。此时 $1 - 0 + 1 = 2$ 成立。

归纳步骤,情形1:某条边位于一个圈上。假设公式对每个边数少于 $E$ 的连通平面图都成立,设该图有 $E$ $\ge 1$ 条边。若某条边 $e$ 位于一个圈上,则去掉 $e$ 后图仍连通(圈的其余部分仍连接其两个端点)。去掉 $e$ 会把它两侧的两个面合并为一个面,于是较小的图有 $V$ 个顶点、$E - 1$ 条边、$F - 1$ 个面。由归纳假设,$V - (E-1) + (F-1) = 2$,化简得 $V - E + F = 2$。

归纳步骤,情形2:没有边位于任何圈上。此时每条边都是桥,即该图完全没有圈,也就是一棵树。画在平面上的树恰好有一个面($F = 1$,唯一的无界区域,因为没有圈可以围出有界区域),而关于树的一个标准事实是:有 $V$ 个顶点的树恰好有 $E = V - 1$ 条边。代入得 $V - E + F = V - (V - 1) + 1 = 2$。

结论。每种情形要么直接得到公式成立,要么(通过去掉一条边)归约到一个由归纳假设成立的更小的图,因此 $V - E + F = 2$ 对任何连通平面嵌入图都成立。