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

我们上次说到，不是所有的平面图都是可4选择的。于是人们接着猜想，是不是所有平面图都是可5选择的呢？1994年，Carsten Thomassen证明了，所有平面图都是可5选择的。这个证明极其简单，论文全文不足两页，证明过程仅十多行。证明对平面图中的区域数n施归纳。有趣的是，归纳的命题比我们待证明的命题要强得多，否则原命题反而证不到。

为简便起见，我们假设平面图是一般的，它没有同属于四块区域的交界点，也没有中空的“洞”。加入这些条件不会让问题变得更简单，因此这些假设都是合理的。下面再假设最外面那一圈区域（与“外部空间”相邻的区域）有s个，它们彼此相连构成了一个环，我们按逆时针顺序把它们分别记为P_1, P_2, P_3, …, P_s。无妨设P_1和P_2的颜色分别为1和2。下面我们证明一个比原命题更强的结论：若最外面那s个区域的颜色列表中至少有三个颜色，其余那些（被围在内部的）区域的颜色列表中有五个颜色，则一定存在合法的列表染色。当区域数n足够小时结论显然成立。

考虑一般情况，如图1。我们标出P_s除了P_1和P_(s-1)以外的邻域，显然它们都是处于内部的、有五个候选颜色的区域。在图1中，s=11，P_11有三个处于内部的邻域T_1, T_2, T_3。现在，把P_11去掉，则剩下的图中P_1, P_2, …, P_10, T_3, T_2, T_1就是新的外围环。注意P_11本来有至少三个颜色可选，除去P_1的颜色，至少还有两种不同的颜色x和y。从T_1, T_2, T_3各自的颜色列表中去掉x和y（如果有的话），这样它们的候选颜色数仍然大于等于3。根据归纳假设，剩下的图存在合法的列表染色。最后，只需要把x或y分配给P_11，使得它和P_10的颜色不同就行了。

一种特殊情况是，万一哪一步我们得到的外围环不是一个单纯的环（如图2）该怎么办？这也很简单，因为我们总可以把它们分解成若干个小环，然后按顺序逐一套用归纳假设。例如在图2中，无妨设P_1和P_2的颜色是已知的，由归纳假设可知环P_1, P_2, …, P_5, P_10及其内部存在合法的列表染色。这样，P_5和P_10的颜色就是确定的了，我们可以把归纳假设再次用于P_10, P_5, P_6, …, P_9及其内部所组成的图形。

可以注意到，我们证明了一个更强的命题其实是不得已而为之，如果直接拿待证命题进行归纳反而推不出结论，因为减少候选颜色必然会破坏掉“有五种颜色”的限制。