三色定理和四色定理

1、7张朝胜四色定理张朝胜淮安市高良涧小学，江苏省淮安市洪泽区，中国Email: ddr123摘 要根据线中顶点的排列顺序推导出二色定理。为不符合四色闭合链、一色定理、二色定理的顶点加辅助线，锁定每个顶点的着色顺序，推导出三色定理。根据一色定理、二色定理、三色定理、链结构的规律推导出四色定理。关键词离散数学，图论，四色定理Four color theoremZhaosheng ZhangHuaian Gaoliangjian Primary School, Hongze District, Huaian City, Jiangsu Province, ChinaEmail: ddr123Abstr

2、actAccording to the arrangement order of the vertexes in the line, the two-color theorem is derived. Add auxiliary lines to the vertexes that do not conform to the four-color closed chain, the one-color theorem and the two-color theorem, the coloring order of each vertex is locked, and the three-col

3、or theorem is derive. According to the one-color theorem, the two-color theorem, the three-color theorem, and the law of chain structure, the four-color theorem is derived.KeywordsDiscrete mathematics, Graph theory, Four color theorem1. 引言英国大学生Francis Guthrie在1852年提出四色问题，四色问题至今没有解决，本文给出四色问题的解决途径。2.

4、四色定理四色问题：任何一张地图用一至四种颜色使有共同边界的国家着色不同。（不包括飞地）地图中的一个国家设为一个顶点，如果2个国家有共同边界，两个顶点连接成1个线段，这个线段是1个边。四种颜色分别是颜色1、颜色2、颜色3、颜色4，在图中分别表示为1、2、3、4。2.1. 一色定理一色定理：平面图中的顶点不连接，平面图中的顶点必然能着色1种颜色。2.2. 二色定理二色猜想：平面图中的闭合线中有N（N是偶数，N4）个顶点，平面图中的顶点必然能着色2种颜色，使连接的顶点颜色不同。证明：平面图中有N（N为自然数，N1）个闭合线（闭合线中有W个顶点，W是偶数，W4），这些闭合线有共用顶点（图1）。平面图中

5、任意2个闭合线（闭合线中有M个顶点，M是偶数，M4），2个闭合线共用偶数个顶点时，每个闭合线有偶数个非共用顶点；2个闭合线共用奇数个顶点时，每个闭合线有奇数个非共用顶点。同理，平面图中的顶点着色2种颜色，每个闭合线中的顶点着色的颜色的顺序不受共享顶点的影响。二色定理成立。Figure. 1. Two color structure图1. 二色结构2.3. 链结构1个闭合线（闭合线中有3个顶点）中有奇数个顶点，这个闭合线中的3个顶点必然且仅仅着色3种颜色。平面图中1个闭合线（闭合线中有3个顶点）以外的顶点被这个闭合线分隔成2个区域，每个区域中的顶点的着色不受另一个区域的影响，等效为每个区域无视另

6、一个区域。一级链结构：N（N为自然数，N2）个闭合线（闭合线中有3个顶点）组成链结构，每个闭合线与另一个闭合线共用M（M为自然数，1M2）个顶点。平面图中的顶点着色3种颜色，闭合线与闭合线共用顶点、顶点（图2左1），顶点、顶点被锁定必须着色同1种颜色。闭合线与闭合线共用顶点（图2左3），顶点、顶点锁定着色2种颜色，顶点、顶点着色的颜色的顺序没锁定。1个链中有一层在同色顶点位置的顶点（图2左1、左2、左3、右3、右2），1个链中能有支链。三色闭合链：1个闭合链中在同色顶点位置的顶点不连接，这个闭合链中的顶点着色3种颜色（图2右3）。四色闭合链：1个闭合链中在同色顶点位置的顶点连接，这个闭合链中的

7、顶点着色4种颜色（图2左2、右2）。1个闭合链中任意1个顶点着色颜色4，例如顶点（图2右2），没着色的顶点不再组成闭合链。1个链结构中有3种颜色的顶点，这个链结构中有N（N为自然数，N3）个闭合线（闭合线中有3个顶点），每个闭合线与另一个闭合线共用2个顶点，这个链结构中的每个顶点着色的颜色的顺序被锁定（图2右1），M（M为自然数，M2）级链结构同理。Figure. 2. 1-level chain structure图2. 一级链结构一个链结构：平面图中的顶点着色3种颜色，每个顶点的颜色的顺序被锁定，这些顶点在同一个链结构中。1个链中的同色顶点是1个链结构中锁定颜色的顺序的顶点，这个链在这个链

8、结构中。N（N为自然数，N1）级链结构：顶点连接顶点、顶点组成2级链结构，顶点、顶点在同1个1级链结构中，顶点、顶点的颜色的顺序被锁定，顶点、顶点的颜色不同。顶点连接顶点、顶点组成3级链结构，顶点、顶点在同1个2级链结构中，顶点、顶点的颜色的顺序被锁定，顶点、顶点的颜色不同。顶点、顶点是链结构中的1级顶点，顶点、顶点、顶点、顶点、顶点是链结构中的2级顶点，顶点、顶点是链结构中的3级顶点（图3）。链结构有N（N为自然数，N1）级，1个N（N为自然数，N1）级闭合链中的1个顶点着色颜色4，例如顶点（图3），没着色的顶点不再组成闭合链。Figure. 3. Multi-level chain str

9、ucture图3. 多级链结构2.4. 三色定理三色猜想：平面图中的闭合链中没有四色闭合链，平面图中的顶点必然能着色3种颜色，使连接的顶点颜色不同。线段的两个端点是任意的颜色，线段中的任意1个顶点着色颜色3，其它的顶点必然能着色颜色1、颜色2，线段中的顶点必然能着色3种颜色（图4左1）。三色结构：三色结构中的每个顶点不在链结构中，每个顶点与N（N为自然数，N3）个顶点连接，每个顶点不符合1色定理、2色定理（图4左2）。为顶点、顶点、顶点加辅助线，辅助线中的辅助顶点连接顶点，组成链结构。顶点和顶点同色时，辅助线中有N（N为奇数）个辅助顶点。顶点和顶点不同色时，辅助线中有M（M为偶数）个辅助顶点。

10、链结构中的顶点必然能着色3种颜色（图4右1、右2）。Figure. 4. Three-color structure图4. 三色结构顶点、顶点、顶点是N（N为自然数，N1）个四色闭合链中的在同色顶点位置的顶点，顶点连接顶点。三色结构中的顶点连接顶点、顶点，为顶点、顶点、顶点加辅助线，辅助线上有M（M为自然数，M1）个辅助顶点，必然增加X（X为自然数，X1）个四色闭合链。原四色闭合链中的Y（Y为自然数，Y1）个顶点着色颜色4，原四色闭合链中没着色的顶点不再组成四色闭合链。当辅助线中有Z（Z为奇数）个辅助顶点时，原四色闭合链中没着色的顶点和辅助顶点有时不组成四色闭合链，有时组成四色闭合链（图5左1

11、）。当辅助线中有W（W为偶数，W2）个辅助顶点时，原四色闭合链中没着色的顶点和辅助顶点必然不组成四色闭合链（图5右1）。只有这种结构加辅助线必然增加四色闭合链，其它结构加辅助线有时不增加四色闭合链。S（S为自然数，S2）级链结构同理。Figure. 5. Four-color closed chain plus auxiliary line图5. 四色闭合链加辅助线平面图中没有四色闭合链，为平面图中的顶点加辅助线，必然能使三色结构和链结构中的每个互相连接的顶点在同1个链结构中。当两个链结构加辅助线合并成一个链结构时，新增的闭合链必然能不是四色闭合链。加辅助线后，必然能不组成四色闭合链，每个链结

12、构中的每个顶点的着色的颜色的顺序被锁定（图6）。如果这个平面图中的顶点必须着色4种颜色，这个平面图中必然有四色闭合链，所以平面图中的顶点必然能着色3种颜色，三色定理成立。Figure. 6. Three color auxiliary line图6. 三色辅助线2.5. 四色定理四色猜想：平面图中有四色闭合链，平面图中的顶点必然能着色4种颜色，使连接的顶点颜色不同。证明：用颜色4为平面图中的每个闭合链中的N（N为自然数，N1）个顶点着色，使每个闭合链中没着色的顶点不再组成闭合链。平面图中1个闭合链以外的顶点被这个闭合链分隔成2个区域，必须有M（M为自然数，1M2）个区域中的顶点没着色，必须先为

13、这个闭合链中的顶点着色，后为顶点没染色的区域中的顶点着色。在本文中设定顶点没染色的区域是内区域，顶点染色的区域是外区域。1个1级闭合链有2层顶点，外层的顶点组成1个闭合线。这个闭合链中的顶点没着色，必然能用颜色4为这个闭合链的内层的N（N为自然数，N1）个顶点着色，例如顶点（图2右2）。在本文中的每种结构中的顶点的连接量取最大值。当1种结构中的顶点的连接量取最大值时，能组成这种结构的每种形态。带：N（N为自然数，N2）层顶点 (顶点的连接量取最大值）组成的结构。平面图中的多个闭合链能共用1个顶点，1个闭合带（闭合带中有2层顶点）中有N（N为自然数，N4）个顶点。顶点在1个链的同色顶点位置，从顶

14、点出发，顺时针方向组成1级链、逆时针方向组成1级链，这个闭合带中有M（M为自然数，0M2N）个1级四色闭合链（图7）。这个闭合带内层有（为自然数，W1）个顶点，当是大于零的偶数时，内层有X（X为自然数，2XW2）个顶点能着色颜色4；当是大于1的奇数时，内层有X（X为自然数，2X（W1）2）个顶点能着色颜色4。平面图中1个闭合带以外的区域被这个闭合带分隔成2个区域，必须有M（M为自然数，1M2）个区域中的顶点没着色，必须先为这个闭合带（闭合带中有2层顶点）中的顶点着色，后为顶点没着色的区域中的顶点着色。1个闭合带（闭合带中有2层顶点）的内层有N（N为自然数，1N3）个顶点外层有M（M为自然数，3

15、M4）个顶点。这个闭合带的内层中必然有1个顶点，这个顶点着色颜色4，没着色的顶点不再组成四色闭合链，例如（图7上左1、左2）（图2左2）。在本文中，除了明确说明的闭合带，其它闭合带（闭合带中有2层顶点）的内层有N（N为自然数，N4）个顶点、外层有M（M为自然数，M4）个顶点。假设顶点连接顶点，顶点、顶点、顶点组成一个闭合线，所以顶点、顶点不能连接。这个闭合带的内层必然有N（N为自然数，N2）个顶点，这些内层的顶点的互相不连接、每个顶点连接外层的M（M为自然数，M2）个顶点，例如顶点、顶点和顶点、顶点（图7上右2右1）。1个闭合带（闭合带中有2层顶点）的内层的顶点连接外层的1个顶点。假设顶点着色

16、颜色4，没着色的顶点组成2个1级闭合链。必须有M（M为自然数，M2）个内层的顶点必然能着色颜色4，但是只有M（M为自然数，M1）个内层的顶点必然能着色颜色4，所以顶点有时不能着色颜色4（图7下左1）。结构：1个闭合带（闭合带中有2层顶点）的内层的顶点连接外层的2个顶点，假设顶点着色颜色4，没着色的顶点组成N（N为自然数，N1）个闭合链。内层中必然有M（M为自然数，M1）个没着色的顶点，这些顶点与顶点不连接、互相不连接、连接外层的W（W为自然数，W2）个顶点、必然能着色颜色4；如果这个闭合带中没着色的顶点组成闭合链，这些顶点必然在这个闭合链中，例如顶点；这些顶点和顶点着色颜色4，没着色的顶点不再

17、组成闭合链（图7下左2）。结构：1个闭合带（闭合带中有2层顶点）的内层的顶点连接外层的N（N为自然数，N3）个顶点，顶点着色颜色4，没着色的顶点不再组成闭合链（图7下右1）。Figure. 7. 2-layer vertexes structure图7. 二层顶点结构增加1次连接：1个闭合带（闭合带中有2层顶点）的内层的2个顶点增加1次连接，增加1个新的边，新增的闭合链共用新边和新边中的2个顶点，例如顶点连接顶点（图8左2）。新边中的1个顶点着色颜色4，新增的闭合链中未着色的顶点不再组成闭合链。结构：1个闭合带内层中的2个顶点互相不连接、各连接外层的2个顶点，为这2个顶点增加1次连接。当内层的

18、顶点连接外层的X（X为自然数，1X2）个顶点时，内层的不增加连接的顶点中，有N（N为自然数，N2）个顶点互相不连接、各连接外层的2个顶点，内层的这些顶点必然能着色颜色4，例如顶点、顶点（图8左1），未着色的顶点不再组成闭合链。当内层的顶点中有顶点连接外层的Y（Y为自然数，Y3）个顶点时，内层的不增加连接的顶点中，有N（N为自然数，N1）个顶点互相不连接、各连接外层的M（M为自然数，M3）个顶点，这些顶点必然能着色颜色4，例如顶点（图8右2），未着色的顶点不再组成闭合链。如果内层的这些顶点在新边的同一侧，一侧的顶点和新边最多组成1个新的四色闭合链，这个四色闭合链内层的1个顶点连接外层的Z（Z为自

19、然数，Z2）个顶点，为这个顶点着色颜色4，这个四色闭合链中未着色的顶点不再组成闭合链；另一侧的顶点和新边最多新组成1个四色闭合链，为这个闭合链内层中的顶点着色颜色4，例如顶点（图8右2），未着色的顶点不再组成闭合链。1个闭合带内层有4个顶点，内层的2个顶点增加1次连接，内层的4个顶点组成链结构，例如顶点、组成链结构（图8左1左2左3）。顶点、和顶点、是新链结构中的同色顶点，并且都着色颜色4，新闭合链中未着色的顶点不再组成闭合链。结构：1个闭合带内层的2个顶点增加1次连接，这2个顶点中有N（N为自然数，N2）个顶点各连接外层的M（M为自然数，M3）个顶点。这2个顶点中的1个顶点必然能着色颜色4，为其中1个顶点着色颜色4，这个顶点连接外层的W（W为自