欧拉公式

设 G 是连通平面图，有 n 个结点，m 条边，r 个面

则有

$$n-m+r=2$$

---

在 平面图 的一个平面表示中：

由边所包围的内部不包含图的结点和边的区域称为 面

包围该面的边构成的 回路 称为 面的边界，边界的长度称为 次数

面积有限的面称为 有限面，反之称为 无限面

无限面只有一个

所有面的次数只和等于边数的两倍

证明

对边数 m 进行数学归纳：

当 $m=1$，分类有没有自环

证明递推：分类是不是树：是树好证明，不是树的话就去掉回路的一条边，面的个数也同样减少 1，递推得出

---

推论

设 G 为一个简单连通平面图，有 n 个结点，m 条边

则有

$$m\le 3n-6$$

运用：证明 $K_5$ 不是平面图（代入上面矛盾了）

---

设 G 为一个简单连通平面图，有 n 个结点，m 条边，每个面的次数至少为 k，则有

$$m\le \frac{k}{k-2}(n-2)$$

运用：证明 $K_{3,3}$ 不是平面图：每个面的次数不能小于等于 3（奇数了），那么都大于等于 4，代入上式得出矛盾

再推论：对于完全二分图来说至少要满足

$$e\le 2(v-2)$$ $$ab\le 2(a+b-2)$$

画图可得，要求任意一边的个数不能超过 2