正多面体の第１の問題は，まずどれだけの種類があるかである（ユークリッドの証明）．それでは第２の問題はとなると

［Ｑ］何種類かの凸多面体を使ってすべての正多面体を作りたい．その最小数は？　　（正多面体元素問題）

であろう．

［Ａ］すべての正多面体を作るには４種類が必要かつ十分であることがわかった・・・しかも，なぜ４種類なのかという理由をこのシリーズでは明確に答えてきたつもりである．

　平面上の地図を塗り分けるには４色が必要かつ十分である（４色問題）・・・４色で塗り分けられることはわかったが，しかし，なぜ４色なのかは依然として謎である．理由が知りたいところであるが，私には何も答えられない．

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

【１】四色問題の解決

　コンピュータ計算による網羅的な探求の例としては，１９７６年，ハーケンとアッペルが４色問題（１８５２年）が正しいことを示したことがあげられる．１８７９種類からなる図形の集合と放電手続きの遂行により，かくして４色問題は４色定理となったのである．その後，ロバートソン，サンダース，シーモア，トーマスによって証明が簡略化されたが，依然，コンピュータに依存した証明である．

　４色問題（平面上の地図を塗り分けるには４色が必要かつ十分である）は素人でも理解できる問題である．４色なければ塗り分けられないような地図を作れば，４色が必要なことは明らかであるから，したがって問題は「４色で十分であることを証明する」か，あるいは「５色以上なければ塗り分けられないような地図を作る」ことである．

　見た目には簡単には思えるが，実は容易に解ける問題ではなく，多くの間違った証明を生み出し，失敗と部分的解決が繰り返されてきた悪名高い問題である．たとえば，１８７９年，ケンペは４色で十分であることの証明し成功したと考えたのであるが，１１年後の１８９０年にヒーウッドにより誤りを指摘された．ケンペの証明は４色で十分であることの証明にはなっていなかったが，５色で十分であることの証明を含んでいたという．以下では四色問題の地図からグラフへの数学化について述べたい．

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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