２０世紀のうちに解決された悪名高き難問に，四色問題
「任意の平面地図は高々４色で色分けできるか？」
がある．５色で色分けできることはヒーウッドによって１００年以上も前から知られていたが，四色問題が肯定的に解決されたのは１９７０年代後半のことで，アペルとハーケンはコンピュータを使ってこの証明を成し遂げた．四色問題の証明は場合分けの数が膨大で，コンピュータによる解析に依存せざるを得なかったのである．
３次元のｎ個の領域を塗り分けるにはｎ色必要な例を作ることができる．それに対して２次元では「どんな平面地図でも４色で塗り分けられる」ことが証明されたのだが，多くの数学者はこの証明においてコンピュータによる解析が本質的だと知ると落胆し，失望したと伝えられている．
その証明は１９９５年にロバートソンらによって改良されてかなり簡単になったとはいえ，いまだ手計算で証明を完成させた人はいない．ともあれ，四色問題がグラフ理論の発展に対する推進力となったことは確かである．
今回のコラムでは，グラム理論の先駆けともいえるオイラーの公式，トーラス面の塗りわけに関するヒーウッドの公式などについて紹介したい．
＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝
【１】オイラーの多面体定理
凸多面体の頂点，辺，面の数をそれぞれｖ，ｅ，ｆとすると，
ｖ−ｅ＋ｆ＝２
が成り立ちます．これは３次元立体について，０次元の特性数であるｖ，１次元の特性数であるｅ，２次元の特性数であるｆの関係を述べたものと解釈されます．
オイラーは晩年の１７年間はまったくの盲目でしたが，それにもかかわらず非常に多くの定理・公式を発見していて，量（ｖ−ｅ＋ｆ）はオイラー標数と呼ばれます．オイラー標数は幾何学において重要な概念である位相不変量の草分けであり，一般に，図形がいくつかの３角形によって分割されているとき，
頂点の数−辺の数＋３角形の数
は分割の仕方によらず定まり，図形に固有な量になるというものです．
平面図形（地図）は１つの面が無限大となって全体が一面に広がってしまった正多面体と解釈することができますから，オイラー標数は１となります．
ｖ−ｅ＋ｆ＝１
しかし，外部領域を含めるならば，多面体の場合と同様に
ｖ−ｅ＋ｆ＝２
が成り立つのです．
また，種数（穴の数）ｇの向き付け可能な閉曲面の場合は
ｖ−ｅ＋ｆ＝２−２ｇ
となることはよく知られています．逆にいうと，多面体の示性数ｇは，ｇ＝１−（ｆ−ｅ＋ｖ）／２で定義される量です．
オイラーの多面体定理を一般化したものが，オイラー・ポアンカレの定理です．オイラー数はベッチ数の交代和
Ｐv−Ｐe＋Ｐf−Ｐg＋Ｐh−Ｐi＋・・・
に等しいというのが，オイラー・ポアンカレの内容ですが，ベッチ数とは，形には関係しないで，接触と分離にだけ関係するトポロジカルな示性数で，簡単にいえば図形の中に潜む種々の次元の穴の数のことです．
凸多角形では，
ｖ−ｅ＝０
ですから，ｎ角形はｎ辺形になりますし，また，胞の個数をｃで表すと，４次元空間では，
ｖ−ｅ＋ｆ−ｃ＝０
というオイラー・ポアンカレの定理が成り立っています．
ところで，線分と三角形および四面体は，それぞれ最も簡単な１次元図形，２次元図形，３次元図形です（単体：シンプレックス）．線分は２つの端点（０次元の境界要素）をもち，その内部は１次元です．三角形は３つの頂点（０次元）と３つの辺（１次元）をもち，その内部は２次元です．四面体は４つの頂点（０次元）と６つの辺（１次元）および４つの面（２次元）をもち，その内部は３次元です．これらの数をまとめて書くと
２，１
３，３，１
４，６，４，１
ですが，これらの数はパスカルの三角形の一部分に相当しています．これから類推すると４次元のシンプレックスは５，１０，１０，５，１，すなわち５つの頂点と１０辺，１０面，５面，５胞（正５胞体）になります．
一般に，ｎ次元単体については，
ｖ＝n+1Ｃ1，ｅ＝n+1Ｃ2，ｆ＝n+1Ｃ3，ｃ＝n+1Ｃ4，・・・，
また，
n+1Ｃ0−n+1Ｃ1＋n+1Ｃ2−n+1Ｃ3＋・・・＋(-1)^(n+1)n+1Ｃn+1＝０
ですから，
Ｐv−Ｐe＋Ｐf−Ｐg＋Ｐh−Ｐi＋・・・＝１±１
すなわち，オイラー標数は，ｎが奇数のとき２，偶数のとき０になることが理解されます．
なお，偶数次元と奇数次元とでの同様の交代性は，超球の体積にも現れます．ｎ次元単位超球{x1^2+x2^2+･･･+xn^2≦1}の体積をｖnとすると，ｖ1=2（直径）,ｖ2=π（面積）,ｖ3=4π/3（体積）はご存知でしょうが，ｖnは漸化式：
ｖn/ｖn-2=2π/n
によって求めることができます．そして，任意のｎに対して，
ｖn=2(2π)^((n-1)/2)/n!! ｎが奇数の場合
ｖn=(2π)^(n/2)/n!! ｎが偶数の場合
であり，１次元から６次元までを具体的に書けば，
ｖn＝２，π，４π／３，π^2／２，８π^2／１５，π^3／６
という具合に，πのべき乗は偶数次元になるたびに１つあがります．
＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝
【２】オイラーの多面体定理と菱形多面体
正多面体の頂点，辺，面の数をそれぞれｖ，ｅ，ｆとすると，ｐｆ＝２ｅ，ｑｖ＝２ｅが成り立ちます．さらに，ｖ＋ｆ＝ｅ＋２が成り立ちますから辺の数ｅは
１／ｅ＝１／ｐ＋１／ｑ−１／２
ｖ＝４ｐ／（２ｐ＋２ｑ−ｐｑ），
ｅ＝２ｐｑ／（２ｐ＋２ｑ−ｐｑ），
ｆ＝４ｑ／（２ｐ＋２ｑ−ｐｑ）
となります．
菱形多面体に対してオイラーの公式を使うと，
４ｆ＝２ｅ，ｑｖ＝２ｅ
ここで頂点を鋭角同士，鈍角同士で合わせると，鋭角の頂点が何面合わさるか（３，４，５のいずれか）に応じて，六面体，（標準的な）十二面体，三十面体の３種類しかできません．
この６，１２，３０という値は正多面体の辺の数と同じですが，一松信先生のお話によれば，これは偶然ではなく，実質的に式
１／ｅ＝１／３＋１／ｑ−１／２ （ｑ＝３，４，５）
で与えられる量とのことです．
三十面体の「ベルト」を押しつぶしてできる二十面体や第２種十二面体では，菱形の鋭角と鈍角の頂点が混じって会する頂点があります．そのため，菱形多面体の分類には少し手間がかかるようです．
＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝
【３】オイラーの多面体定理と星形正多面体
凹型正多面体まで含めると，正多面体は全部で９種類あり，プラトンの立体と呼ばれる凸型５種類の他の４種類は，星形正多面体（ケプラーがみつけた星形小十二面体，大十二面体と約２００年後にポアンソがつけ加えた星形大二十面体，大二十面体の４種類）です．星形正多面体は４種類しかないことはコーシーが示しています．
オイラーの多面体定理より，凸多面体に対してはｇ＝０となります．ところが，４種類の星形正多面体のうち，２種類はｇ＝０ですが，残りの２種類はｇ＝４になります．ｇ＝４はトポロジカルにいえば穴が４つあるドーナツと同一ですから，ｇ＝０のみを星形正多面体と呼ぶべきだとの主張もあります．
なお，同じ大きさの正４面体２個による相貫体＜ケプラーの８角星＞はダビデの星の３次元版ですが，星形正多面体には加えません．さらに，一様多面体（準正多面体の星形化）は７５種類，ザルガラー多面体（すべての面が正多角形である凸多面体）は正多面体，準正多面体を除くと９２種類存在します．
＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝
【４】オイラーの公式の使い方
正則とは限らない一般の多面体では
Σｐi＝ｐ1＋・・・＋ｐf＝２ｅ，
Σｑi＝ｑ1＋・・・＋ｑv＝２ｅ
となります．ｐi≧３，ｑi≧３ですから
２ｅ≧３ｆ，２ｅ≧３ｖ
このことから多面体は７本の辺をもつこと（ｅ＝７）は不可能であることが証明されます．
（証）ｅ＝７なる多面体が存在したと仮定すると，３ｆ≦１４，３ｖ≦１４．ｆ，ｖは面，頂点の個数なので，３より大きな整数でなければならない．したがって，ｆ＝４，ｖ＝４，ｅ＝７となるが，これはオイラーの多面体定理
ｖ−ｅ＋ｆ＝２
を満たさないので矛盾が生じる．
このことから
ｆ≧４，ｖ≧４，ｅ≧６（ｅ≠７）
であることがわかりましたが，他にオイラーの多面体定理で示される制限はないのでしょうか？
ｖ−ｅ＋ｆ＝２，２ｅ≧３ｆ，２ｅ≧３ｖ
を組み合わせると，
２ｖ＋２ｆ＝２ｅ＋４≧３ｆ＋４ → ｆ≦２ｖ−４
２ｖ＋２ｆ＝２ｅ＋４≧３ｖ＋４ → ｖ≦２ｆ−４
これらはシュタイニッツの定理（１９０６年）と呼ばれますが，オイラー自身すでに
ｆ≦２ｖ−４，ｖ≦２ｆ−４
という結果を知っていたようです．
また，別の組合せ方をすると，
３ｖ＋３ｆ＝３ｅ＋６≦２ｅ＋３ｆ → ３ｆ−ｅ≧６
３ｖ＋３ｆ＝３ｅ＋６≧２ｅ＋３ｖ → ３ｖ−ｅ≧６
も得られます．
つぎに，３次元立体では必ず頂点に結合する辺の個数が３の頂点か３角形の面をもつことを示します．ｎ本の辺をもつｆn枚の面とｎ本の辺が交わるｖn個の頂点をもつ凸多面体について，
i)Σｎｆn＝Σｎｖn
ii)Σｆ2n+1は偶数
iii)ｖ3＋ｆ3＞０
を順に示していきます．
（証）各辺は２個の頂点をもつから，Σｎｖn＝２Ｅ．また，各辺では２枚の面が交わるからΣｎｆn＝２Ｅ．
（証）ｉ）より，Σ（２ｎ＋１）ｆ2n+1＝（偶数），したがって，Σｆ2n+1も偶数．
（証）Ｅ＝Σｅn，Ｖ＝Σｖn，Ｆ＝Σｆn，Σｎｆn＝Σｎｖn＝２Ｅ． もしｖ3＝０，ｆ3＝０ならば，２Ｅ＝４ｖ4＋５ｖ5＋・・・≧４Ｖ．同様に，２Ｅ≧４Ｆ．これより，Ｖ−Ｅ＋Ｆ≦Ｅ／２＋Ｅ／２−Ｅ＝０．これはオイラーの多面体定理：Ｖ−Ｅ＋Ｆ＝２に矛盾するから，ｖ3，ｆ3のうち，少なくとも１つは０でない．
さらに，オイラーの多面体定理で示される制限からいえることとして，
Ｆ＝ｆ3＋ｆ4＋ｆ5＋・・・
２Ｅ＝３ｆ3＋４ｆ4＋５ｆ5＋・・・
を
６Ｆ−２Ｅ≧１２
に代入すると
３ｆ3＋２ｆ4＋ｆ5−ｆ7−２ｆ8−３ｆ9−・・・≧１２
地図のように２つの辺に囲まれた領域まで許すことにすると，この数え上げ公式は
４ｆ2＋３ｆ3＋２ｆ4＋ｆ5−ｆ7−２ｆ8−３ｆ9−・・・＝１２
となります．いずれにせよ，係数が１ずつ小さくなり，それが０となるｆ6は式中に現れません．
このことから，ｆ3，ｆ4，ｆ5の少なくとも１つは０でない→多面体には３角形か４角形面か５角形面が少なくとも１つなければならない，同様に，多面体の少なくとも１つの頂点は３次か４次か５次でなければならない→すべての頂点の次数が６以上となることは不可能であり，必ず次数が５以下の頂点をもつことが導き出されます．これもオイラーが知っていた結果であるということです．
ここで，
(1)ｆ2＝ｆ3＝ｆ4＝０だとすると，少なくとも１２個のｆ5がなければならないことになる
(2)多面体の面がすべてｆ5とｆ6であるならば，ｆ5＝１２（切頂二十面体）
(3)多面体の面がすべてｆ4とｆ6であるならば，ｆ4＝６（切頂八面体）
(4)多面体の面がすべてｆ4，ｆ6，ｆ8であるならば，ｆ4＝ｆ8＋６（斜方切頂立方八面体）
これらの結果は極めて重要で，四色定理の証明の中核をなしています．
＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝
【５】ヒーウッドの公式
オイラーの公式は単純ですが，要はその使い方というわけで，たとえば，多面体には３角形か４角形面か５角形面が少なくとも１つなければならないことはもっと簡単に証明できます．
どの領域も少なくとも６つの領域で囲まれていると仮定すると
６ｆ≦２ｅ
また，このような問題を解くにあたっては，すべての交点で３本の境界線が会している地図だけを考えればよいので，
３ｖ≦２ｅ
これらをオイラーの公式に代入すると
ｖ−ｅ＋ｆ≦１／３ｅ−ｅ＋２／３ｅ＝０≠２
となって矛盾を生じます．したがって，５個以下の隣接領域しかもたない領域が少なくともひとつあることになります．
平面や球面上に描かれた地図に関するオイラーの公式は
ｖ−ｅ＋ｆ＝２
でしたが，トーラス上の地図に関するオイラーの公式は
ｖ−ｅ＋ｆ＝０
です．
トーラスでは６個以下の隣接領域しかもたない領域が少なくともひとつあることを証明するために，どの領域も少なくとも７つの領域で囲まれていると仮定すると
７ｆ≦２ｅ
また，３ｖ≦２ｅですから
ｖ−ｅ＋ｆ≦２／７ｅ−ｅ＋２／３ｅ＝−１／２１ｅ≠０
という矛盾を引き出すことができます．
したがって，トーラスでは６個以下の隣接領域しかもたない領域が少なくともひとつあることになります．このことを利用すると，
「トーラス上のどんな地図でも７色で塗り分けられる」
ことが証明されます．ヒーウッドは実際に７色を必要とする例もあげています．
これを証明したヒーウッドはさらにｇ個の穴があいたトーラス上の地図に関するオイラーの公式
ｖ−ｅ＋ｆ＝２−２ｇ
を利用して
(1)２個の穴があいているトーラス上の地図はどれも８色で塗り分けられる
(2)３個の穴があいているトーラス上の地図はどれも９色で塗り分けられる
・・・・・・・・・・・・・・・・・・・・・・・・
(3)１０個の穴があいているトーラス上の地図はどれも１４色で塗り分けられる
に引き続いて，
(4)ｇ個の穴があいているトーラス上の地図はどれもＨ（ｇ）色で塗り分けられる
Ｈ（ｇ）＝［｛７＋√（１＋４８ｇ）｝／２］
を証明しました．
［・］はガウス記号で，
ｇ：１，２，３， ４， ５， ６， ７， ８， ９，１０
Ｈ：７，８，９，１０，１１，１２，１２，１３，１３，１４
となるのですが，しかし，ヒーウッドはｇ≧２に対してそのような地図が実在することを示すことはできませんでした．そのため，この問題は「ヒーウッド予想」と呼ばれることになりました．
１９６８年，リンゲルとヤングスは，ｇ個の穴のあいているトーラス上にこれだけの色を必要とする地図が存在することを証明したのですが，ヒーウッド予想（１８９０年）が最終的に証明されるまでには７７年もの歳月が必要だったというわけです．
＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝
【６】四色問題
平面上の四色問題では，地図が平面ではなく球面上に描かれているものとすると，外部領域は他の領域と何の違いもないことになります．したがって，外部領域を塗っても塗らなくても構わないことになり，平面上の四色問題は球面上の四色問題と等価と考えることができます．
ヒーウッドは五色定理を鮮やかに証明できても，四色定理を証明することはできませんでした．したがって，平面・球面上の四色問題よりも先に，トーラス上の地図の塗り分けには７色必要であることが証明されたことになります．
ヒーウッドの式はｇが正の数の場合にしか適用できないのですが，仮にｇ＝０を代入するとＨ（０）＝４となって，穴のあいていないトーラスすなわち球の表面に置かれた地図を塗り分けるために必要な色の数を正しく導き出すことができます．しかし，残念ながらこれは偶然の一致であり，ヒーウッド予想の証明から四色定理を導くことはできません．
大きい種数ｇに対するヒーウッドの公式は四色問題が証明されるよりもかなり前に証明されているのですが，種数０の場合，つまり平面的集合の場合が最も難しいという事実は注目すべき事です．
四色問題の証明では，地図を電気回路とみなして
４ｆ2＋３ｆ3＋２ｆ4＋ｆ5−ｆ7−２ｆ8−３ｆ9−・・・＝１２
の条件の下の放電（電荷の移動）に帰着させる（放電法）のですが，この手続きにはどうしてもコンピュータが必要になりました．アペルとハーケンの後も放電法の改良が続けられ，１９９４年，ロバートソン，サンダース，シーモア，トーマスの４人が新たな１章をつけ加えたことは冒頭に記したとおりです．
しかし，これとて基本的にはアペル，ハーケンと同じコンピュータ路線なのです．確かにコンピュータを使った証明を美しいあるいはエレガントな数学と呼ぶことはできないかもしれません．コンピュータを使わない証明にはこれまでにないようなまったく新しいアイディアが必要になると思われるのですが，そうしたアイディアは今日もなお登場していないのです．
＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝
【参】クロムウェル「多面体」シュプリンガー・フェアラーク東京
ウィルソン「四色問題」新潮社
最近入手したこれらの本を読んでみると，教えられる点が多いのに驚かされます．確かにこういった歴史的な面からまとめた日本語の本が（翻訳以外に）余りないのが残念です．
＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝