■平面グラフの頂点彩色(その26)

【6】クラトウスキーの定理(1930年)

 「与えられたグラフGが平面グラフである必要十分条件は,GがK3,3とK5をマイナーとして含まないことである.」

 クラトウスキーの定理によれば,K3,3とK5は平面上に枝を交差させることなく描くことができないし,平面上に描くことさえできない.この定理を使うと4色定理は

 「K3,3とK5をマイナーとして含まないグラフは,頂点を4色で彩色することが可能である.」と言い換えることができる.なお,トーラス面上の地図の塗り分けには7色必要な場合がある.

===================================

K3,3とK5はクラトフスキグラフである。

===================================