グラフの幾何学的安定性は

［１］１次元

　　ｅ≧ｖ−１

［２］２次元

　　ｅ≧２ｖ−３

［３］３次元関節下

　　ｅ≧３ｖ−６

［４］ｎ次元関節下

　　ｅ≧ｎｖ−ｎ（ｎ＋１）／２

　　ｎは次元数，ｎ（ｎ＋１）／２はｎ次元単体の辺数

で表される．

　ちょっと紛らわしいのだが，平面グラフに対しては

　　ｅ≦３ｖ−６

が成り立つ．

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

　　２ｅ≧３ｆ

オイラーの公式に代入すると

　　ｖ−ｅ＋ｆ＝ｖ−ｅ＋２ｅ／３≧２　→　ｅ≦３ｖ−６

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

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

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

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

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

　　４ｆ≦２ｅ

より，

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

となって矛盾．

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

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

　　ｆ＝２＋ｅ−ｖ＝５

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

　　２０＝４ｆ≦２ｅ＝１８

となって矛盾．

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

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

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

　　ｆ＝２＋ｅ−ｖ＝７

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

　　２１＝３ｆ≦２ｅ＝２０

となって矛盾．

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

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

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

　　ｆ＝ｅ−ｖ＝３

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

　　１２＝４ｆ≦２ｅ＝１８

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

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

　　ｆ＝ｅ−ｖ＝５

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

　　１５＝３ｆ≦２ｅ＝２０

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

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

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

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

【４】トーラス面上のＫ7

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

　　ｆ＝ｅ−ｖ＝９

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

　　２７＝３ｆ≦２ｅ＝３０

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

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

　　ｆ＝ｅ−ｖ＝１４

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

　　４２＝３ｆ≦２ｅ＝４２　　（正則）

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

［３］もし，Ｋ8が平面的であるならば，ｖ＝８，ｅ＝２８．

　　ｆ＝ｅ−ｖ＝２０

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

　　６０＝３ｆ≦２ｅ＝５６

となって矛盾．

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

【５】球面上のＫ4

　もし，Ｋ4が平面的であるならば，ｖ＝４，ｅ＝６．

　　ｆ＝２＋ｅ−ｖ＝４

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

　　１２＝３ｆ≦２ｅ＝１２　　（正則）

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

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