1922 年费兰克林证明了每个有至多25个国家的地图都可以用四种颜色着色。1926年雷诺德将这一结果推广到27个国家，然后在1938年费兰克林又创造了31个国家的纪录。1940 年温恩证明了35个国家的情形以后，这方面的研究有所停滞，直到1970年，奥尔和史坦普尔对所有至多包含40个国家的地图证明了四色定理。在哈肯和阿佩尔最终证明四色定理而使所有这类结果都黯然失色以前，这个数字曾经达到了96。

1950年德国数学家希许就曾估计，证明四色猜想大概要涉及一万个不同构形。虽然后来证明他的估计是过分夸大了，但它却正确地指明了，四色问题也许只有借助于能处理巨量数据的强有力的计算装置才能获得解决。

1972年哈肯与阿佩尔联手，经过整整四年的紧张工作，终于在1976年6月他们用三台计算机花费了1200个计算机小时，处理了两千多个构形，才算验证了四色问题成立。可对于数学家来说肯定是不满意的。

——————

吴哲先从着色判定问题入手：设已知一个图g和m>0种颜色，在只准使用这m种颜色对g的结点着色的情况下，是否能使图中任何相邻的两个结点都具有不同的颜色呢?

再从m-着色最优化问题则求可对图g着色的最小整数m。这个整数称为图g的色数。这是求图的最少着色问题，来求出m的值。

for(i = 1; i<= n; i++)

{

if(DFS(0， i))

{

cout <<“the min colors :“<< i << endl;

break;

}

}

------