8.2 欧拉公式

数学学习 · 爱知数学讲义

18
本章目录 · 1 节

本章导读

【欧拉公式的来源与计数约定】把凸多面体的一个面看作外部面,其棱和顶点组成连通平面图,得到顶点数、边数、面数之间的恒等式。本节都对已经固定的平面嵌入计面,外部面必须算一次;记顶点数为 ,边数为 ,面数为 ,连通分支数为 。边数按实际边计,平行边分别计数,自环也是一条边,不能先化成简单图再沿用原来的面数。

【定理8.2.1:欧拉公式】任意有限连通平面图满足

这里允许自环和平行边,不要求图为简单图;但必须连通。按边数 作归纳:当 时,连通性迫使图只有一个顶点,故 ,等式成立。设所有边数为 的连通平面图已经满足公式,考察有 条边的图。

若图是树,取一片树叶 ,连同它的唯一关联边删去。剩下的图仍连通,。树叶边是桥,不围出新面,删除它不会合并两个不同的面。因此

若图不是树,就有一条边 在某个圈上。删去 后图仍连通,顶点数不变;该边两侧原属两个面,删边将二者合为一个面,故 。于是

以上涵盖自环所围成的圈以及两条平行边围成的圈。若想一次看清计数,也可保留一棵生成树:先后删去 条非树边,每删一条就减少一个面,最终树只有外部面,因此 。不要把删桥也当成“面数减1”。

【定理8.2.2:非连通情形的推广】若平面图有 个连通分支,则

事实上同一式对 也适用,退化为欧拉公式。设第 个连通分支单独画出时有 ,则 ;总顶点、总边数满足 。各分支单独计算时各有一个外部面,合起来整个平面只有一个无界区域,所以

即使一个分支位于另一个分支围成的面内,上式仍成立:各分支总共围出 个有界区域,外部区域另加1。将各分支的等式相加,有

整理即得结论。孤立顶点也是一个分支,不产生新的面。8.1图8.1.2中 ,恰有 ;若误用连通版,面数就会少算1。

【定理8.2.3:连通图的面次数下界与边数上界】设连通平面图的每个面次数都至少为 ,其中 ,则

由面次数握手定理,;再代入 ,得到

由于 ,除法不改变不等号方向,即得上界。等号成立当且仅当每个面次数都恰为 。这里 是所有面的统一下界,外部面也不能例外;桥在面边界上出现两次,必须按两次计算。不能只看到“无三角形”就不加条件地宣称每个面都是一个长度至少4的圈,因为有桥的图中面边界可能重复边。

【推论8.2.1:两个基本非平面图】 与 都不是平面图。

先反设 可平面。它是5顶点10边的简单图,且没有桥,每个面的次数至少为3,故 ,与 矛盾。

再反设 可平面。它有6顶点9边,是没有桥的简单二部图,既无自环、重边,也无奇圈,所以面次数至少为4。由 的上界,,与9条边矛盾。证明采用的是“假设存在平面嵌入后必违反计数”,而不是根据某幅图有交叉就下结论。

【定理8.2.4:非连通图的边数上界】若平面图有 个连通分支,每个面次数至少为 ,则

补全推导:由推广的欧拉公式得 ,代入 ,可得

再除以 即得。等号同样要求每个面次数都恰为 。有些分支是孤立点并不妨碍此式,但仍须满足“每个面次数至少为 ”的前提;整个图没有边时外部面次数为0,就不能套用这个定理。

【定理8.2.5:极大平面图的边数】 的简单极大平面图满足

由8.1定理8.1.4,图必连通;由定理8.1.5的必要性,每个面都是三角形,故 。把 代入,解得两式。比如图8.1.4(c)有8点18边12面:,,且 。条件 不可省去: 按定义也极大,但不满足这个边数等式。

【推论8.2.2:简单平面图的通用边数界】任意 阶简单平面图,无论是否连通,都满足

在固定的有限顶点集上持续添加仍保持可平面性的简单边,有限步后到达极大平面图。由刚证明的定理,该图有 条边,原图的边数不超过它。这个推理只用极大平面图的三角面性质,不依赖尚待证明的充分性,避免循环论证。

也可直接处理连通情形:简单连通图至少3点时,每个面的边界次数至少3,树的唯一外部面次数为 ,故可以取 。非连通图可在不同分支间补边连通而不引入交叉,再用同一界。这个上界只是可平面性的必要条件,满足它不能保证可平面;若违反它,则可立即判定非平面。对含自环或重边的图不可直接使用这个简单图上界。

【定理8.2.6:简单平面图中必有低度顶点】非空有限简单平面图的最小度满足 。若 ,简单性给出每个顶点度至多 。若 而假定每点度至少6,则由顶点握手定理 ,即 ,与 矛盾。

所以“至少存在一个度不超过5的顶点”总成立;它不表示每个顶点度都不超过5,也不表示图的最大度不超过5。更一般地,任意非空子图仍为简单平面图,也有这样的顶点,这一点将在着色中使用。空图没有顶点,通常不定义最小度,不应把存在性断言套到它上面。

【补完定理8.1.5的充分性】现设 的简单连通平面图每个面次数都等于3。由 与 ,得到 。若存在不相邻的两点 ,加边后仍可平面,新图仍简单且顶点数不变,但边数为 ,与通用上界矛盾。因此它确为极大平面图。这证明排除了所有可能的重画方式,比仅观察当前画法“没有空地方加边”更严格。