４，グラフの頂点彩色
単純グラフGの隣接するどの2頂点も異なる色になるようにGのすべての頂点を色分けすることをGの頂点彩色という。k種類の色によるGの頂点彩色をGのk-彩色といい、Gがk-彩色できるとき、Gはk-彩色可能であるという。
グラフの頂点vに色を塗ることを頂点vを着色するという。
グラフGがk-彩色可能で、かつ(k-1)-彩色可能でないとき、グラフGはk-染色的であるという。
定理４・１(四色問題)
すべての平面的グラフは4-彩色可能である。
1976年にスーパーコンピュータを利用して証明された。
