放電法，Ｄ可約性，Ｃ可約性

　四色問題では，二〜四辺国は可約配置だが，五辺国は違った。四色問題における可約配置の不可避集合を初めて見つけたのはアッペルとハーケンだが，可約配置の不可避集合はただ一通り存在するのではない。現に可約配置の不可避集合は複数セット見つかっている。二辺国，三辺国，四辺国はこれらの集合の要素であるが，五辺国はそうではない。可約配置の不可避集合は，少なくとも数百の可約配置を要素としてもつ。では二〜四辺国以外の可約配置はいったいどんなもので，どうやって見つけられたのだろう？きちんとした説明は私の手に余るが，その概略だけ紹介したい。
　可約配置とは，最小反例には絶対に含まれない配置で，複数の国々からなるのが普通である。例えば，早くに可約性が分かった配置に，「バーコフのダイヤモンド」というのがある。これは，四つの五辺国からなる配置で，1913年にその可約性が証明された。「配置」であるから，単に五辺国が四つあればいいわけではなく，その並び方がポイントである。これら四つの五辺国の隣接関係が以下のようになっている場合が，バーコフの発見した「ダイヤモンド」である。それは，自分以外の三国と隣接する五辺国が二つ，二国とだけ隣接する五辺国が二つあるような配置だ。二つの五辺国Ａ，Ｂ同士が隣接し，それらＡ，Ｂに阻まれて，残り二つの五辺国Ｃ，Ｄ同士が隣接していないような配置である。これら四つの五辺国は，六つの国に取り囲まれている。
　この周囲六国と，さらに外側の国々からなる地図Ｍが四色で塗られていれば，中心の四つの五辺国を含めた地図Ｍ’も四色で塗れる。これはすごい。地図Ｍは真ん中に国がない穴のあいた地図で，その穴の周りの国数が六国である必要はあるが，それ以外の制約はない。それさえ満たせば，Ｍがどのような配置の地図であろうと，四色でどのように塗られていようと，バーコフのダイヤモンドを入れて国が四つ増えた地図Ｍ’も必ず四色で塗れるのだ。それが可約性（実は後述のＤ可約性）である。
　四辺国の可約性は，ケンペ鎖を使って簡単に確認できた。しかし，バーコフのダイヤモンドの可約性検証はなかなか骨である。四辺国でも場合分けをしたが，もっと多くの場合分けをして，すべての場合に五色目が要らなくなることを確かめなくてはならない。ともかく，その仕事は百年前にバーコフがやってくれた。
　さて，集合｛二辺国，三辺国，四辺国，バーコフのダイヤモンド｝が，もし不可避集合なら，その時点で四色問題は解決していたのだが，もちろんそんなことはない。二〜四辺国もバーコフのダイヤモンドも含まない地図など簡単に見つかる。可約配置をいくらたくさん見つけても，それらを要素とする集合が，不可避集合にならなければ意味がないのである。そうすると，バーコフのように単なる思いつきでつくった配置について，その可約性を確かめていくというのはいかにも迂遠だ。もっとも，はじめのうちは，可約配置の不可避集合がそんなにばかでかい集合になるとは思われていなかったようで，この調子でも何とかなるか？という感じだったのかもしれない。
　この点の効率化には，ヘーシュの発案した放電法の利用が大変大きく貢献した。ヘーシュは，四色問題にほとんど生涯をかけた数学者である。この放電法は，オイラーの多面体定理をもとにして，ある配置があり得ない配置かどうかを簡易に判定する手法である。先に五辺以下国存在定理を証明するのに，オイラーの多面体定理を直接用いたが，あのやり方をもっとうまく工夫したものが放電法だ。詳細は省くが，この放電法をどう使うかというと，次のようである。
　まず，ある不可避集合を想定する。例えば，｛二辺国，三辺国，四辺国，五辺国｝が不可避集合であることは分かっているので，これをもとに，｛二辺国，三辺国，四辺国，隣接する二つの五辺国，隣接する五辺国と六辺国｝という集合を考える。そして，この集合が不可避集合でないと仮定して，背理法によりこれが不可避集合であることを証明する。｛二辺国，三辺国，四辺国，五辺国｝が不可避集合であって，かつ｛二辺国，三辺国，四辺国，隣接する二つの五辺国，隣接する五辺国と六辺国｝が不可避集合でないなら，｛二辺国，三辺国，四辺国，隣接する五辺国と七辺以上国｝が不可避集合のはずだ。もし，二〜四辺国を含まない地図で，「隣接する五辺国と七辺以上国」も含まない地図があり得ない（存在しない）ことが証明できれば，｛二辺国，三辺国，四辺国，隣接する五辺国と七辺以上国｝は不可避集合でないことが示されて，矛盾が出る。放電法は，「そんな地図はあり得ない」というところを証明する段階で使う。
　こうようにして，放電法で新しい不可避集合を探す。そして，得られた不可避集合の要素が可約配置であるかどうかを判定する。もし，可約配置であると判定できない要素があれば，その要素が入らないようにまた別の不可避集合を探す。隣接する二つの五辺国も，隣接する五辺国と六辺国も，可約と判定できないなら，それらを要素に含まない別の不可避集合を放電法を使ってつくるのだ。この繰り返しで，不可避集合はどんどん大きく（要素が多く）なっていくが，いつかは可約配置だけからなる不可避集合が得られるだろう。もちろんこれは希望で，この手順に終わりがなく，いくらでも要素の数が増えていくのかもしれない。
　可約性の検証がこれまた難しい。可約配置は20世紀に入って次々に見つかったが，与えられた配置が可約かどうかを調べる手法は系統的とはいえずいきあたりばったりだった。六国に囲まれたバーコフのダイヤモンド程度なら手計算できても，周囲の国数が増えるにつれて検証の手間は指数関数的に増える。コンピュータの利用が不可欠になってくる。アッぺルとハーケンは最終的に十四国に囲まれた配置まで調べたが，これはコンピュータ以前には絶望的に不可能だった。それに，ある配置が可約でないことを示すのは，悪魔の証明みたいなもので，可約性を厳密に調べることは極めて困難だ。
　そこでヘーシュは可約より厳しい条件であるＤ可約，Ｃ可約という概念を導入した。Ｄ可約，Ｃ可約のチェックであれば，コンピュータで比較的効率的にできる。チェックが効率よくできるように可約性の条件を狭くしたのである。Ｄ可約性のチェックの方がＣ可約性より容易。そこで，ある配置がＤ可約かどうかを調べ，Ｄ可約でなければＣ可約かどうかを調べるという手法をとる。Ｄ可約でもＣ可約でもない要素が残れば，その不可避集合はあきらめて次の不可避集合をつくる。但し，Ｄ可約でもＣ可約でもないからといって可約でないとは限らない。Ｄ又はＣ可約であることは，可約であることの十分条件であり，必要条件ではない。
　放電法とＤ可約，Ｃ可約。ヘーシュが編み出したこの武器が，実は四色問題解決に直結した。このあとは大胆なやまかけで計算量を減らしたり，アルゴリズムを工夫したりといった小手先（？）の技巧が奏功して，証明が達成されたのだ。そして個人の能力・アイデアというよりも，どれだけ強力なコンピュータをどれだけの時間使えたか，というある意味で人間臭い要素が，四色問題をめぐる競争に決着をつけた。ハーケンはポアンカレ予想から転向し，同じドイツ人のヘーシュに教えを乞うて四色問題に取り組んだ。しかしその後二人は別々に研究をすすめ，アメリカで仕事をしたハーケンが四色問題の解決者として歴史に名を残す。老数学者たちが，「これは数学なのか？」と慨嘆したのも無理はない。