【６】クラトウスキーの定理（１９３０年）

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

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

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

＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝

【７】トーラス面上のＫ3,3とＫ5

［１］もし，Ｋ3,3が平面的であるならば，ｖ＝６，ｅ＝９．

　　ｆ＝ｅ−ｖ＝３

また，各面は少なくとも４つの辺をもたなければならないから，

　　１２＝４ｆ≦２ｅ＝１８

となって矛盾は生じない．

［２］もし，Ｋ5が平面的であるならば，ｖ＝５，ｅ＝１０．

　　ｆ＝ｅ−ｖ＝５

また，各面は少なくとも３つの辺をもたなければならないから，

　　１５＝３ｆ≦２ｅ＝２０

となって矛盾は生じない．

［Ｑ］土地を５つの区域に分ける．どの区域も他の４つの区域と接していなければならない．道路を他の４つの区域に交差しないようにつなぐことはできるか？

［Ａ］平面では実現不可能であるが，トーラス面では可能で，実際，これらのグラフは平面的としてトーラス面上に描くことができる．

＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝