【１】完全２部グラフＫ3,3の問題

［Ｑ］ガス・水道・電気の３種類のライフラインを３軒の家に交差しないようにつなぐことはできるか？

［Ａ］ｖ＝６，ｅ＝９，３ｖ＝２ｅ

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

　　４ｆ≦２ｅ

より，

　　ｖ−ｅ＋ｆ≦２ｅ／３−ｅ＋ｅ／２＝ｅ／６＝１．５＜２

となって矛盾．

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

　　ｆ＝２＋ｅ−ｖ＝５

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

　　２０＝４ｆ≦２ｅ＝１８

となって矛盾．

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

【２】完全グラフＫ5の問題

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

　　ｆ＝２＋ｅ−ｖ＝７

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

　　２１＝３ｆ≦２ｅ＝２０

となって矛盾．

　結局，Ｋ3.3とＫ5を含グラフはどうやっても平面グラフにはならず，失敗に終わる運命にある（クラトウスキーの定理）．

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

【３】クラトウスキーの定理

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

　Ｋ3,3とＫ5は平面上に枝を交差させることなく描くことができないし，平面上に描くことさえできない．この定理を使うと４色定理は

　「Ｋ3,3とＫ5をマイナーとして含まないグラフは，頂点を４色で彩色することが可能である．」と言い換えることができる．

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