动机
一个图可以含有一个度数很高的顶点,却仍然容易染色。对合适的贪心顺序而言,重要的不是初始最大度数,而是在剩下的图中能否总能删去一个低度顶点。把这样的删除顺序反过来,就能在每一步限制已染色邻点的个数。
欧拉(Euler)的平面图边数上界恰好给出这种可反复使用的低度保证,并立即推出六种颜色足够。要得到五种颜色,唯一的困难在于度数为五的顶点:它的邻点可能已经用完了所有颜色。在一个更小的平面图中收缩两个不相邻的邻点,会迫使它们共用一种颜色,从而为被删去的顶点腾出一种颜色。证明将说明,为什么普通的收缩在没有额外处理时不能总是还原。
论证使用由欧拉公式得到的简单平面图边数上界 。本文不声称证明了四色定理。
定义
定义 10.4.1
(退化度与删除顺序)
对非负整数 ,若有限简单图的每个非空子图都含有一个度数至多为 的顶点,则称该图为 -退化的。这里的度数是在该子图内部计算的。退化删除顺序是指每一步删去一个当前度数至多为 的顶点,直到没有顶点为止。
正常顶点染色给每个顶点指定一种颜色,并使相邻顶点的颜色不同。按给定顺序的贪心染色,是给每个顶点指定第一种尚未被其已染色邻点使用的颜色。
检验退化性只需检验导出子图。事实上,在选定顶点集上的任何子图中,各顶点的度数都不超过该顶点集上导出子图中的度数。导出子图中的低度顶点,在进一步去掉一些边之后仍是低度顶点。因此,删去顶点或边时该性质得以保持。
定义 10.4.2
(边收缩及简单图的整理)
收缩一条边,是把它的两个端点等同为一个顶点,保留其余所有关联关系;若希望结果为简单图,则再删去自环并合并重边。平面性得以保持:在平面嵌入中,在该边及其端点的一个细小邻域内把所选的边缩短,并让关联的边端随之移动。远离新的公共端点之处,各曲线可以保持分离。删去自环或重复的边不会引入交叉。
这种局部作图操作只说明收缩后的图仍是平面图,并不是把其染色提升回原图的一般规则。如果原先相邻的顶点后来被赋予合并顶点的同一种颜色,它们之间原有的边就违反了正常性。我们将收缩一个由三个顶点构成的结构,并且只把颜色提升到原本不相邻的两个顶点上。
定理/命题
定理 10.4.3
(退化序给出受控的贪心染色)
一个图是 -退化的,当且仅当其顶点有一种删除顺序,使每个顶点至多有 个排在其后的邻点。把该顺序反过来并贪心染色,至多使用 种颜色。每个有限简单平面图都是 5-退化的,因而是六可染色的。
对以邻接表表示的平面图输入,维护度数的队列可在 时间内给出删除顺序和一个六染色。该算法构造一个染色;仅仅找到这样的顺序,并不能证明任意输入是平面图。
定理 10.4.4
(通过收缩证明五色定理)
每个有限简单平面图都有一个由五种颜色构成的色板中的正常顶点染色。该结论包括非连通图和空图。证明使用归纳法、欧拉的度数上界,以及对一个五度顶点的两个不相邻邻点的收缩。
六染色算法与五色存在性证明是两种不同的产出,其构造也不同。后一个证明是构造性的,但这里不断言其反复收缩与提升的任何优化实现的复杂度上界。两个定理都没有说每个平面图都需要五种颜色。
证明思路或证明
证明
(删除顺序与逆序贪心染色)
对 -退化图,在剩下的导出子图中反复选取低度顶点。它在当时的邻点恰好就是它在删除顺序中排在其后的邻点。反过来,给定这样的顺序,取任意非空子图,选其中最早的顶点。它在该子图中的所有邻点都排在其后,故其在该子图中的度数至多为 。这证明了等价性。
按相反的顺序,每个顶点至多有 个已染色的邻点。它们至多禁用 种颜色,于是 种颜色中至少还有一种可用。每当一个顶点被染色,它都避开所有先前已染色的邻点。因此,每条边的两个端点一旦都被染色,颜色就不同。
证明
(平面图的 5-退化性与线性六染色)
每个至少有三个顶点的非空简单平面子图都满足已证明的上界 。其度数和为 ,因此有一个度数至多为五的顶点。当只有一个或两个顶点时,由简单性可直接得到同样的结论。所有子图仍然是平面的。因此,低度观察不仅适用于开始时,而是可以反复使用,从而证明了 5-退化性。
对于线性时间的删除算法,先初始化所有顶点的当前度数,并建立由度数至多为五的顶点组成的队列。删去其中一个顶点时,将每个尚存邻点的度数减一,并在某个邻点的度数首次降到五时把它加入队列。度数从不增加,因此每个顶点只需入队一次。每条边只引起常数次度数更新,而平面图的低度保证使得只要还有顶点,队列就不会为空。在反序中,检查各邻点并使用一个含六项的颜色标记,这同样花费 。
证明
(收缩一对不相邻邻点得到五染色)
对五染色,对顶点数进行归纳。空图已经染好色。在非空平面图中,选取度数至多为五的顶点 。若其度数至多为四,则删去它,由归纳法给较小的图染色,再给它指定一种未出现在其至多四个邻点上的颜色。
还需处理度数恰为五的情形。它的邻点中有两个,设为 ,彼此不相邻。否则这五个邻点会导出 ,而这在平面图中不可能:其十条边违反了五个顶点上简单平面图至多九条边的上界。依次收缩 与 ,把 合并为一个顶点,并作简单图整理。所得的图是平面图且顶点数少二,所以由归纳法它有一个五染色。
还原除 以外的每个原顶点,让 和 取得合并顶点的颜色,其余顶点保持原色。这在 上是正常的。被还原的两个顶点之间没有边,而且从其中任一个到其他原顶点的每条边,都作为从合并顶点到该顶点的一条边保留了下来。因此不可能再出现冲突。
在 的五个邻点中, 现在共用一种颜色;其余三个至多再贡献三种颜色。因此在 处至多有四种颜色被禁用。选取第五种可用颜色,即完成归纳。合并顶点在收缩过程中代表 ,但提升染色时有意让原来的 保持未染色,直到这最后一步。
证明透视
只有不相邻的那一对继承合并后的颜色
三个假设在三个不同位置用到。平面性经由简单上界 提供度数至多为五的顶点 ;平面性又排除了 ,所以 有两个邻点 不相邻。平面图在收缩下封闭,才使归纳假设能用于合并 之后的图;单靠 5-退化性并不足够,因为 是 5-退化的。 与 不相邻,才使提升是正常的:若有边 ,它会连接两个同色顶点;若把合并后的颜色也给 ,便会与 、 冲突,所以 暂不染色。
计数随即完成归纳。提升之后,由于 与 同色, 的五个邻点至多呈现四种颜色,五种颜色中便有一种空出。若有六个邻点,同样的做法可能留下多达五种被禁止的颜色;这就是论证需要度数五、而不只是某个小度数的原因。
为什么该证明不能变成四色定理的证明
欧拉的上界给出一个度数至多为五的顶点,但不能据此假定其度数至多为三。在五个邻点中合并一对,把它们可能的颜色数降到四。这在五种颜色的色板中留下一种可用颜色,但在四种颜色的色板中可能一种也不剩。因此,这一归纳恰好证明它所陈述的界。不能靠最后把色板大小改个标号而得到另一个定理。
收缩这一步用到的也不止退化性。它需要收缩后的较小图仍留在平面图类之内,这样才能对该图使用归纳。一个任意的 5-退化图可能需要六种颜色,六顶点完全图就是例子。该图类在证明所用的图运算下封闭;这种结构上的封闭性提供了仅由删除顺序所没有的信息。
例题详解
例题 10.4.5
(退化度避免了过大的最大度数上界)
一个有一个中心和任意正数个叶子的星图是 1-退化的。含边的非空子图有度数为一的叶子,无边的子图度数为零。先删叶子再删中心,然后反序染色:中心得到一种颜色,所有叶子得到第二种颜色。最大度数可以任意大,而这个顺序始终只用两种颜色。由于存在边,一种颜色不可能足够。
例题 10.4.6
(收缩五邻点轮图的中心)
取一个五顶点外圈 和中心 。选取不相邻的外圈顶点 ,把它们与 合并为顶点 。其余顶点为 。在整理后的图中, 与这三个顶点都相连,另外还有边 。
给 染颜色一, 染颜色二, 染颜色三。把颜色一提升到 ,其余保持不变,再给 染颜色四。这是原图的一个正常染色。这里确实需要四种颜色:奇数长度的外圈至少需要三种,而这三种在与它们都相邻的中心处全部被禁用。一般的五色上界对具体某个图不必是紧的。
例题 10.4.7
(在树上,坏的贪心顺序可以使用任意多种颜色)
令 为单个有根顶点。对 ,取 的不相交副本,再添加一个新根,与它们的根相邻。结果是一棵树:每个旧分支恰好用一条边连到新顶点。由归纳得 。
先按递归规定的顺序给每棵复制的树染色,最后给新根染色。被复制的各个根得到颜色一至 ,所以新根得到颜色 。因此这个贪心顺序在一棵树上用了 种颜色,尽管当 时这棵树是可二染色的。一个平面图得到很多种贪心颜色,可能只是因为处理顺序不好;这并不推翻存在性上界。
概念视角结构
删除与收缩使用不同种类的封闭性
低度顶点的删除控制反序贪心的每一步。收缩则改变了在提升解时哪些顶点必须共用一种颜色。平面图在这两种运算下都保持平面性,从而可以对不同的较小图使用归纳。每种运算都保持了下一步所需要的性质,而它们提升染色的规则并不相同。
常见错误
反例模式
子式的染色不能总是原封不动地提升
收缩三角形的一条边。去掉由此产生的重边之后,所得的图是一条边,可二染色。三角形却不可二染色:它的第三个顶点与任一条边的两个端点都相邻。把被收缩的相邻端点以同一种颜色还原是行不通的。五色证明避开了这个错误:只让原本不相邻的邻点共用一种颜色,并单独给居中的顶点染色。
常见错误
(一个低度顶点不等于退化顺序)
不要误以为初始度数低就保证在所有剩余的图中都有低度顺序。在 上接一个悬挂顶点:图中有度数为一的顶点,但删去它之后,剩余每个顶点的度数都是四。这个图是 4-退化而非 1-退化的,而且需要五种颜色。
常见错误
(能找到顺序并不证明平面性)
不要以为一个染色或一个删除顺序能证明图是平面的。对 ,队列算法仍然找到每个顶点至多有五个后继邻点的顺序,并输出一个六染色;然而 有十五条边,多于平面上界十二。
常见错误
(含自环的图不在定理范围内)
简单性对度数和染色的陈述至关重要:含自环的图在通常的相邻端点规则下没有正常顶点染色,无论调色板多大,因为带自环的顶点与自身相邻。
总结
退化度把反复删除低度顶点转化为受控的反序贪心顺序。欧拉的上界为平面图提供了这种顺序,由此得到线性时间的六染色。经过细致提升的收缩处理了五度顶点这一障碍,证明了五色定理,同时也恰好说明了为什么同样的论证不能证明四色定理。
练习
快速检查
(证明六顶点完全图是 5-退化的,但不是五可染色的。说明平面图的收缩证明还用到了哪一条额外的性质。)
检验每个子图的度数上界以及团的染色要求。
解答 · 答案
的每个子图至多有六个顶点,因而度数至多为五,所以它是 5-退化的。六个顶点两两相邻,因此需要六种不同的颜色。它不是平面图,因为十五条边超过了上界十二。平面图的证明用到了平面性在收缩下的保持,以及所选邻点之间不含五元团;这些事实不能仅由 5-退化性推出。
快速检查
(解释为什么仅仅得到一个度数至多为六的顶点,并不能通过合并一对不相邻的邻点来完成同样的五色归纳。)
数一数合并之后邻点可能具有的不同颜色数。
解答 · 答案
有六个邻点时,合并一对不相邻的邻点,只迫使这两个共用一种颜色。其余四个邻点可能再使用四种颜色,于是在被删去的顶点处至多有五种颜色被禁用。这样,五色色板中就没有保证可用的空闲颜色。论证需要度数为五的结论,才能把被禁用的颜色数降到至多四。这说明了该证明的局限,并不是断言每个度数为六的结构都真的需要六种颜色。
快速检查
(证明对五顶点的奇圈,退化度给出的上界是紧的。给出一个明确的最优染色,并指出带自环的版本为什么不在该定理的范围之内。)
比较 2-退化性与沿奇圈交替使用两种颜色的不可能性。
解答 · 答案
五圈的每个顶点度数为二,且每个子图都有度数至多为二的顶点,所以它是 2-退化的。沿其五条边交替使用两种颜色,会回到起点而得到相反的所需颜色,这是不可能的。按圈的顺序,颜色一、二、一、二、三给出一个有效的三染色。因此其色数为三,达到 。加上一个自环会使其端点与自身相邻,所以没有任何颜色能满足正常性;所得的图不是简单图,被排除在两个定理的假设之外。