一。七色定理

二证明

三意义

一。七色定理

起源，人类在企图证明四色定理过程中，发现了在曲面上作图，反而更加容易。1974年德国的林格和美国的杨斯证明了：Np=[(7+√1+48P)12].(公式来自《图论导引》214页，机械工业出版社)

P是指这个曲面的洞的个数，又叫亏格。当亏格为1时N1=[(7+√1+48×1)12].=7

外国数学家并且给出了这个需要7种颜色染色的图形：（参见右图）上下对折，再左右对折，形成一个汽车轮胎形状，就是有7个区域两两相连。

表明：在有一个洞的曲面上染色，6种颜色是不够的。如果能够将一个图G画在平面上，使得他的边仅仅在端点相交，则称这个图是可以嵌入平面的，或者称其为平面图。

二证明

又叫Heawood定理。 人类在企图证明四色定理过程中，发现了在曲面上作图，反而更加容易。1974年德国的林格和美国的杨斯证明了：Np=[(7+√1+48P)/2].证明这个公式，数学家用了78年。P是指这个曲面的洞的个数，又叫亏格。当亏格为3时：N3=[(7+√1+48×3)/2]=9（公式来源：

《图论导引》214页，机械工业出版社，

《图论导引》258页，人民邮电出版社）

《图论和网络流理论》239页，高等教育出版社?

介绍

需要7种颜色染色的图形：下图是全景图，上图：上下对折，再左右对折，形成一个汽车轮胎形状，就是有7个区域两两相连。

表明：在有一个洞的曲面上染色，6种颜色是不够的。

如果能够将一个图G画在平面上，使得他的边仅仅在端点相交，则称这个图是可以嵌入平面的，或者称其为平面图。

证明部分在证明四色定理过程中，

Heawood的文章不仅仅指出了Kempe的错误，而且也给出了五色定理的一个证明，然而他没有停留于此，Heawood继续考虑其它一些想法，Heawood文章的主要后续成果是征对于可嵌入到球面的图的最大色数问题。Heawood把注意力转移到其它曲面上图的色数确定问题上。

对于非负整数k，设

χ（Sκ）=max{χ（G）}.

其中，max取遍嵌入到Sx的所有图G,自Kempe的1879年的文章之后，大家都相信χ（Sò）=4，而在Heawood的1890年的文章之后，仅仅知道χ（Sò）=4，或者χ（Sò）=5.

1976年当Appel和Haken宣布其成果之后，确定了χ（Sò）=4(四色定理)。

在Heawood的1890年的文章中，他试图获得关于χ（Sκ）的一个公式，在其中k为正整数，事实上，他认为他已经做到了，然而，他所做的仅仅是获得了χ（Sκ）的一个上界。

定理; 对于每一个正整数k，

χ（Sκ）≤[(7+√1+48K))/2]

证明：（直接证法）设G为看嵌入到Sκ的一个图，并且设

h=[(7+√1+48K)/2],

由h的定义可以证明：

6+12（k-1）/h=h-1

下面证明χ（G）≤h

在G的所有诱导子图中，设H具有最大的最小度，根据定理：对每个图G，

X(G)<1+max{S（H）}

其中，max取遍G的所有诱导子图H。

可以得到X(G)≤1+δ(H),假设H的阶为n，边数为m，若n≤h，则δ（H）≤n-1，X(G)≤n≤h，因此我们可以假设n>h.

由于G可以嵌入到Sk，所以，H也能够嵌入到Sk，因此由推论可知

K>γ(H)≥m/6-n/2+1，

易见，m≤3n+6（k-1），因此nδ(H)≤Σdegu=2m≤6n+12（k-1）所以，

δ(H)≤6+12(k-1)/n ≤6+12（k-1）/h=h-1。从而，X(G)≤1+δ(H)=h=[(7+√1+48k)/2]。

，结论成立。

证明这个公式对于所有整数k成立又花费了78年。数学家Gerhard Ringel和Ted Young对这个公式的证明发挥了最主要的作用。

上下对折再左右对折就是一个轮胎形状，有7个区域两两相连。它有1个洞。1974年德国数学家林格（Gerhard Ringel）和美国数学家杨斯(Ted Youngs)证明：Np=[(7+√1+48k)/2]；k表示洞的数目。N1=[(7+√1+48x1)/2]=7，当k=1时，N1=7。

三意义

区域染色的意义十分重大，在实际生活中有广泛的应用。