ベルジェ（Berge）は理想グラフの研究の初期に２つの予想を定式化した．

［１］グラフが理想グラフであるときに限り，補グラフは理想グラフである（弱理想グラフ予想）．

［２］グラフが理想グラフであるときに限り，グラフもその補グラフも長さが５以上の奇数サイクルを含まない（強理想グラフ予想）．

［１］は任意の理想グラフの補グラフも理想グラフであることを述べたもので，１９７２年ロヴァース（Lovasz）によって肯定的に証明された．

　当時多くの学者がこの証明に挑戦していたが，なかでもファルカーソンはこれが成り立たないと考えてアプローチしていたために証明に失敗した．彼はロヴァースによって肯定的に証明されたことを知るや否や，直ちにその証明ができたと伝えられている．

　ファルカーソンはその数年後（１９７６年），失意のうちにこの世を去ったが，研究の厳しさを教えられるはなしである．

［２］が証明されたのはずっと後のことで，２００２年にチュドノフスキー，シーモア，ロバートソン，トーマスの４人のよって解決された．なかでもマリア・チュドノフスキーは若くてきれいな女性だったこともあり，かなり注目を集めたとのことである．

　グラフ理論における最近の大きな成果であるが，与えられたグラフが理想グラフであるかどうかを判定する多項式時間アルゴリズムもチュドノフスキーらによって設計開発されている．

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

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

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

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

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

　　４ｆ≦２ｅ

より，

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

となって矛盾．

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

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

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

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

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

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

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

【３】ワグナーの分解定理

　「Ｋ5をマイナーとして含まないグラフは，平面グラフと８点からなる特殊なグラフから生成可能である．」

　この定理より「Ｋ5をマイナーとして含まないグラフは，頂点を４色で彩色することが可能である．」が４色定理と同値であることがわかる．

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

【４】ハドヴィガー予想（１９４３年）

　「Ｋkをマイナーとして含まないグラフは，頂点を（ｋ−ｌ）色で彩色することが可能である．」

　ｋ＝５の場合が４色定理に相当しますから，ｋ≧６の場合は４色定理より強いことを主張しているというわけである．１９９３年に，ロバートソン，シーモア，トーマスによってｋ＝６の場合が証明された．ｋ≧７の場合は現在解明されていない重要な問題の中で，最も難しい予想のひとつと考えられている．

　さらに，ロバートソンとシーモアはハドヴィガー予想が多項式時間で解決可能であることを証明した．このように彼らの取り組みは，離散数学の中でもとくにグラフ理論，アルゴリズム分野において数多くの深遠な結果と大きな前進をもたらしたのである．

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