经典证明：列表染色与可选择数（上）

四色定理告诉我们，给地图上的每个区域涂一种颜色，为了使相邻的区域有不同的颜色，我们总共只需要4种颜色就够了。不过，万一有些省装怪，偏不喜欢分配给它的颜色该咋办？这下问题就变得有意思起来了。为了满足不同省市的要求，国家测绘局可以在为地图染色前先让每个省市列出自己能够接受的几种颜色，染色时就只从每个省市给出的候选颜色中取色。我们把每一个使得相邻区域的颜色互不相同的染色方案叫做一种列表染色(list coloring)。现在的问题是，至少要求每个省市列出多少个候选颜色才能使合法的列表染色总是存在，不管这些颜色列表是什么？如果每个省市列出k种颜色就足够了，我们就称该地图是可k选择的(k-choosable)。或许大家会想，k=4就够了吧，毕竟四色定理保证了只使用4种颜色一定能实现合法的染色，而在列表染色问题里总的颜色很可能还不止4种，同时相邻区域的公共颜色数量也将减少。但是，数学家们早就注意到，能够k着色的平面图不见得就一定可以k选择。例如，下面这个图显然可以二着色，但它就不是二选择的——如果每个区域的颜色列表如图中所示，则不存在满足要求的列表染色。因此，人们普遍认为，并不是每个平面图都是可4选择的。

不过，数学家们一直没能找到不可4选择的平面图。1993年，Voigt发现了第一个不能4选择的平面图，它有238块区域。构造方法非常具有启发性，从里面能看到不少数学思维方法。

来看看这个图是怎么构造的。整个图是建立在图1的基础上的，它有10个区域，每个区域的颜色列表都是(1,2,3,4)。图中有12个顶点打了一个小圆圈标记，这12个顶点都是两块白色区域和一块阴影区域的交界处。在每个这样的交界处“挤”进去一块新的区域，如图2。新区域的颜色列表也是(1,2,3,4)。

我们以A、B、F三块区域的交界处为例。挤进去一个区域P后，图形中又产生了两个阴影部分与白色部分的交界点，我们也用小圆圈来标记。再在区域A、P、F间挤进去9块区域，如图3所示；在区域B、P、F的交界处插入图3的镜像，即让图3的F和P等于图2的F和P，图3的A则相当于图2的B。对图1的那12个交界点中的每一个都进行这样的操作，我们便得到了一个有10+12*19=238块区域的图形。

下面我们说明，这个地图没有合法的列表染色方案。这个构造的核心就在于，我能强制某个区域涂上指定的颜色，从而制造一些冲突。在图1中，区域A、B、C、D两两相邻，因此一定有一个区域涂了颜色1。如果A是颜色1，注意A、B、D、E也是两两相邻的四块区域，则B、D、E只能分别着颜色2、3、4，那么区域L一定染颜色1；如果B是颜色1，类似地可知M一定是颜色1；如果D是颜色1，同样区域F一定是颜色1；最后，如果C是颜色1，由于C、B、D、T两两相邻，因此B、D、T分别涂颜色2、3、4，区域N只能是颜色1。总之，图中的4个阴影部分中必然有一个涂了颜色1。无妨假设F染了颜色1。注意它周围一圈三块区域分别是颜色2、3、4，这三块区域两两相邻。标出颜色2和颜色3所属的区域，无妨假设是A和B（即A=2、B=3，或者A=3、B=2）。无论如何，A、B、F中间的区域P的颜色都是4。

假设A=2、B=3。如图3，A、F、P的颜色都已经固定了，并且T1、T2、T3都只剩下(3,5)两种颜色可选，X、Y和四块斜线区域都只剩下(3,5,6)可选。考虑X的颜色，若它选了6，则周围一圈区域R1到R4只能分别是3、5、3、5或者5、3、5、3，无论如何T1都没有颜色可选；若X选了5，则R1到R4只能是6、3、6、3（此时T3无从选择）或者3、6、3、6（此时Y只能选5，T2将无从选择）；最后，若X选择颜色3，类似地要么T3没有可选的颜色，要么T2没有可选的颜色。该图没有合法的列表染色。

再考虑A=3、B=2的情况。于是B、F、P的颜色都固定了，并且它内部的情况与图3（的左右镜像）完全一样。于是我们证明了，整个图都是不能4选择的。