5色图包含子式K-5的一个简单证明 (2006年)

### 5色图包含子式K-5的一个简单证明 #### 概述 本文献针对Hadwiger猜想中的一个重要特殊情况进行了研究，即当图G可以被5种颜色正确着色时（简称5色图），图G必然包含一个子式K-5。此处K-5指的是完全图K5去除一条边后的图。这一结论与著名的四色定理紧密相关，当k=5时，Hadwiger猜想实际上等价于四色定理。因此，这一结论不仅为Hadwiger猜想提供了一个重要的特例证明，也为四色定理提供了可能的新证明路径。 #### Hadwiger猜想背景 Hadwiger在1943年提出的猜想是图论中的一个重要问题。该猜想表述为：如果图G可以被k种颜色正确着色，则G包含一个子式Kk。特别地，当k=5时，这个猜想等价于四色定理。四色定理指出，任何地图都可以用不超过四种颜色着色，使得相邻的区域颜色不同。虽然四色定理已经通过计算机辅助方法得到了证明，但是寻求更为直观、简洁的数学证明一直是图论领域的一个重要目标。 #### 主要概念及引理 为了理解本文的主要结论，需要先了解以下几个关键概念： - **k顶点着色**：对于图G，使用k种颜色为图中的每个顶点分配一种颜色，使得相邻的顶点颜色不同。 - **图的色数**：图G的色数χ(G)是使得图G可以被正确着色的最小颜色数量。 - **顶点割**：如果从图G中移除一组顶点T之后，G变为非连通图，则称T为图G的一个顶点割。 - **连通度**：图G的连通度k(G)定义为使得图G非连通所需的最小顶点割的大小。对于完全图，其连通度定义为其顶点数减1。 - **收缩操作**：对于图G中的一条边e，若将e的两个端点合并成一个新的顶点，并移除所有自环边，则称执行了一次边e的收缩操作。 - **子式**：如果图H可以通过图G或G的子图经过一系列的边收缩操作得到，则称H为G的一个子式，记作H<G。 接下来，介绍几个关键的引理，这些引理在证明过程中扮演了重要角色： - **引理1**：如果图G是k临界的，则对于G的每一个真子图H都有χ(H)<χ(G)，同时满足σ(G)≥k-1。这里σ(G)表示图G中任意三个顶点的度数之和的最小值。 - **引理2**：临界图的顶点割不是团。 - **引例3**：临界图是二连通的，即至少需要删除两个顶点才能使图非连通。 #### 证明过程 在证明的过程中，作者首先利用了引理1至引例3以及相关的定义，构建了一个严密的逻辑框架。具体来说，通过分析5色图的性质和结构，结合引理中的条件，作者展示了如何从5色图中找到一个包含子式K-5的过程。这一证明过程的关键在于理解和应用上述定义和引理，特别是关于连通性、顶点割以及子式的概念。 通过这样的证明，不仅为Hadwiger猜想提供了一个特例的解答，同时也为四色定理的进一步研究提供了新的思路。此外，这种方法避免了复杂的计算机辅助验证，为图论中的经典问题提供了更加直观和简洁的数学证明。 #### 结论 本文献通过对5色图的研究，给出了5色图包含子式K-5的一个简单证明，不仅深化了对Hadwiger猜想的理解，也为四色定理提供了新的证明方向。这一成果对于推动图论领域的理论发展具有重要意义。