动机
同一个图有许多画法。一张图上的交叉可能仅是画法造成的,而非图本身的性质。平面性问的是:能否找到一种画法,使边只在共同端点相交?面数恒等式把这种几何存在性问题转化为顶点数与边数的算术限制。这里讨论有限简单无向图,并区分抽象图与它的某个嵌入。
定义
定义 3.1.1
(平面嵌入、平面图与面)
平面嵌入把每条边画成连接两端点的简单弧,不同边仅能在共同端点相交,顶点也不能落在边的内部。若图存在平面嵌入,称之为平面图。从平面中去掉图形后得到的连通区域称为面,包括无界的外面。
一个图可以有不同的嵌入和画法;选作外面的区域不是抽象图的固有顶点或边。
对不连通画法,把一个面的边界长度定义为所有边界分量上关联边侧的总数;若桥的两侧都属于该面,就计两次。孤立顶点不贡献边侧。
定义 3.1.2
(合法染色与色数)
顶点的合法染色为每个顶点分配颜色,使相邻顶点颜色不同。色数 是合法染色所需颜色数的最小值。
孤立顶点不会对其他顶点施加限制。平面嵌入是否存在,与某个染色用了多少颜色,是不同的问题;但平面性可以帮助推出染色上界。
定理/命题
定理 3.1.3
(连通平面图的欧拉(Euler)公式)
有限连通平面图有 个顶点、 条边和 个面时,。
定理 3.1.4
(简单平面图的边数界)
有限简单连通平面图若有 个顶点,则 。
概念视角组合
有界面的个数就是生成树以外的边数
把公式改写为 。连通图的生成树有 条边,所以右边数的是树以外的边,也就是这棵树决定的基本圈个数。下面的证明逐步实现这个计数:每次删去的圈边都在最后剩下的生成树以外,而每次删除都减少一个有界面。因此在同一个图的每个平面嵌入中,有界面的个数都相同,尽管它们的形状可以不同。
证明思路
证明
(删除圈边直至剩下生成树)
我们使用若尔当(Jordan)曲线定理:平面中的简单闭曲线把平面分为内部和外部,该曲线是两者的共同边界。先设连通图是树。它有 ,其平面画法只有一个面:从单顶点开始,每次添加叶边不会围出区域,因为新边不形成闭曲线。因此 。
若图不是树,取圈上一条边删除。其余圈边提供替代路径,所以删除后仍连通。画在平面上的该边分隔两个不同面:它与圈的其余部分形成简单闭曲线,故边的两侧局部属于补集的不同分支。删除该边恰好合并这两个面,因此 都减少一, 不变。重复操作直到留下生成树;边数有限,过程终止,树的情形便证明恒等式。
证明透视
平面在证明中的位置
计数部分很简单;拓扑只出现在两处。树的情形用到:添加一条叶边不会围出区域,因为只在一个端点与原图相交的新弧不在任何闭曲线上。归纳步骤恰好使用一次若尔当曲线定理:圈上的一条边与该圈其余部分构成简单闭曲线,所以它的两侧属于不同的面,删除它恰好使 减少一。选取圈上的边正是两方面都成立的原因:它保持图连通,又保证两侧是不同的面;若删除的是桥, 不变而图会不连通。有限性使删除过程停止,而连通性这一假设保证终点是一棵满足 的生成树。
证明
(计算边侧)
为证明边数界,计算面与边侧的关联。每条边有两侧,对面边界长度之和贡献二;即使桥的两侧属于同一个面也要算两次。至少有三个顶点的简单连通平面图,每个面的边界长度至少为三:长度一需要自环,长度二要么需要重边,要么将仅有两个顶点的连通分支中唯一一条边走两次。因此 。代入 ,得 ,即 。
反例模式
简单性与三个顶点都不可省略
声称:每个 的连通平面图,不论是否简单,都满足 。画一个三角形,并在每条边旁、三角形外侧再画一条平行弧。这个连通平面多重图有 、,欧拉公式给出 :内部三角形面、外面,以及平行弧之间三个长度为二的面。但 。长度为二的面正是简单性所排除的。顶点数条件也需要:单条边有 ,而 时 。两种情形中欧拉恒等式本身仍然成立;失效的只是面长度的界。
例题详解
例题 3.1.5
(五顶点完全图)
完全图 的每对顶点之间有边,故 。五顶点简单连通平面图至多有 条边。矛盾证明 非平面,无须检查所有画法。
例题 3.1.6
(带对角线的正方形)
正方形加一条对角线有 。将对角线画在正方形内部,得到两个有界三角面和一个无界面,所以 ,而 。边数界给出 ,与画法一致。但不等式本身不能构造嵌入,画法才提供存在性。
例题 3.1.7
(画在平面上的树)
四顶点路径有三条边、一个面,因此 。按边侧重数计算,该面的边界长度为六:三条桥的两侧各出现一次。若错误地假设每条边属于两个不同面,计数就会出错。
常见错误
反例模式
必要边数界不能判定平面性
是平面性的必要条件,不是充分条件。 有 ,满足 ,却不是平面图,下文将用更强的界证明。反过来,一张画法有交叉也不意味着图非平面:正方形两条对角线交叉的画法表示 ,而把一个顶点放在三角形内可以画出无交叉的嵌入。
常见错误
(欧拉公式需要计入分支数)
两个分离的三角形有 ,而不是 。若对不连通的画法套用 ,会预言只有 个面,漏掉一个三角形内部。正确的常数是 ,见不连通画法一节的证明。
常见错误
(桥的两侧属于同一个面)
四顶点路径唯一的面边界长度是六而不是三:三条边的两侧都会遇到。若每条桥只计一次,面长度之和便是 ,与面长度之和等于 这一恒等式矛盾,而本节所有边数界都依赖这个恒等式。
总结
欧拉恒等式针对固定的平面嵌入;边数界是抽象平面图的推论。违反必要界可以证明非平面,通过必要界不能证明平面性。存在桥时,计算面边界要按边侧重数计数。
练习
快速检查
(连通平面图有 个顶点和 条边,有多少个面?)
解答 · 答案
欧拉公式给出 ,其中包括外面。
快速检查
(七顶点简单连通平面图能否有 条边?)
解答 · 答案
不能,因为边数界要求 。
二部图的更强边数界
定义 3.1.8
(二部图)
若顶点可以分成两组且每条边都连接不同组,称图为二部图。
定理 3.1.9
(二分平面图的边数界)
对至少有三个顶点的有限简单连通二分平面图,。
证明
(长度至少为四的面)
每走一条边就换组,所以任何闭游走长度为偶数。至少有三个顶点的简单连通二分平面图,每个面边界长度至少为四:前面的论证排除长度一和二,二分性排除奇数长度。即使边界游走重复经过桥,这个结论也成立。
计算边侧得 ,代入 ,得到
的两组各有三个顶点,每一对跨组顶点之间有边,所以 ,但上界要求 。因此 非平面。普通的 界没有检测出它;二分性的额外假设改进了结论。
起作用的是面长度条件,而不是二部图这个名称本身。若简单连通平面图每个面边界长度至少为 ,则 ,结合欧拉公式可得
边界长度必须包含桥的重复边侧。不能未经检查就把某个围长代入:树没有圈,却仍然有面边界游走。
快速检查
(八顶点简单连通二分平面图能有 条边吗?)
解答 · 答案
不能,二部图界给出 。这是对所有平面画法的不可能性证明,不只是否定某次尝试。
按顺序染色
一个简单的染色上界不需要平面性。设有限非空图的最大度数为 。任意排列顶点,依次从 种颜色中选色。轮到一个顶点时,至多有 个邻点已经染色,因此至多 种颜色被禁止,至少还剩一种。于是 。
完全图 表明这个上界可以达到:每对顶点相邻,不能共享颜色。对具体图,不同顺序可能产生不同的颜色数,但同一上界仍然有效。因此贪心染色是“这些颜色足够”的证书,通常不是颜色数最小的证明。
例。 四顶点路径最大度为二,通用界给出至多三种颜色。沿路径交替使用两种颜色得到合法染色;因为存在边,一种颜色不够。因此其色数为二,最大度界在此不紧。
四色定理给平面图更强的普遍上界,但这里不提供证明,也不能仅用最大度界推得。有限非空简单平面图有度数至多五的顶点。若 ,每个顶点的度数至多为一。若 ,使用下文证明的不连通情形推广 :度数和 ,不可能每个顶点的度数都至少为六。但只靠这个平均值步骤不能证明四色定理,还需要额外思想。
快速检查
(证明至少有一条边的非空森林可以用两色染色,且色数恰为二。)
解答 · 答案
每棵树选一个根,按顶点到根距离的奇偶染色。每条边连接相邻层:若一条边连接相同奇偶的层,利用通向根的唯一路径和该边会形成圈。因此相邻顶点异色。孤立顶点可取任一色。至少有一条边,其端点必须异色,所以一种颜色不够。
快速检查
(平面画法有 ,且每个面边界长度为四。它有多少个面?)
解答 · 答案
不存在这样的画法。每条边有两侧,所以各面边界长度之和为 。若每个面的长度都是四,这个和就是 ,而 没有整数解。这个论证既不用欧拉公式,也不用连通性。若仍套用连通形式的公式,会得到 个面,但其边界长度之和将为 。
不连通的画法
连通性是上述欧拉公式形式的重要条件。
定理 3.1.10
(含 个分支的欧拉公式)
对有 个连通分支的平面图,
证明
(用桥连接各分支)
可以在平面上添加 条边连接不同分支而不引入交叉。每条新边都是桥,所以不会产生新面。所得连通平面图有相同的顶点数和面数,边数为 ;应用连通欧拉公式并整理即得结果。连接弧可画在各面内部;若一个分支位于另一分支的圈内,先通过包含它的面把它连到该面的边界。重复直到所有分支连通。
例如两个分离的三角形有 :一个外面及每个三角形内部各一个面。因此 ,右边不能误写为二。孤立顶点也是一个分支,但不产生新面;添加它时 同时增加一,公式仍一致。
使用边数界时,应先处理小图或不连通图,不能盲目套用针对连通图的推导。对于 的简单平面图, 确实也适用于不连通的情形:可在同一顶点集上添加不交叉的边,将各分支连成简单连通平面图。连接两个不同分支的边不会与已有的边平行,所以扩大后的图仍是简单图;对它应用连通情形的界,得 。上面的面计数假设连通,不连通情形正是靠这个加边步骤来证明。