如果有人声称图论中的某个问题被外界所熟悉，那一定是指下面的四色定理 (four colour theorem)(这个定理蕴含着：每个地图最多只需四种颜色来着色)： 定理5.1.1（四色定理）每个可平面图是4可着色的 关于四色定理证明的一些讨论和其历史，可以参考这一章最后的注解.在这里， 我们证明下面较弱的形式 定理5.1.2（五色定理）每个可平面图是5可着色的. 证明设G是一个有n≥6个顶点和m条边的平面图.我们归纳地假设，有 个具有少于n个顶点的平面图均是5可着色的.由推论4.2.10，有 dG=2m≤23n-6 1<6. 个人研使用 设v∈G是顶点度不大于5的顶点.由归纳假设知，图H:=G一v存在一个顶点 着色V(H)一{1，·，5.如果v的邻点最多用了4种颜色，那么c可以扩充为 图G的一个5着色.所以我们可以假设顶点v恰有5个邻点，且每个邻点着有不 同的颜色 设D是一个足够小的包含v的开圆盘，使得它只与关联v的五条边的直线 段相交.我们按照这些线段在D中的循环位置列举为1，·，s5,并且假设v是 包含s:的边（亿=1，·，5，见图51.1）.不失一般性，我们可以假设对于每个，有 c()=i