アルゴリズムの最先端に挑戦：「四色定理」はどこまでバランスよく塗れるのか？

こんにちは、米田寛峻 (square1001) です！

Qiita では、前回記事 直感でわかる、ヒューリスティック問題の羅針盤 ～貪欲法から山登り法まで～ 以来 4 年ぶりの投稿になります。

私も大学院の修士 2 年生になって、最先端の研究に取り組むようになりました。主にアルゴリズム分野の研究を行っています。ですので、本記事では アルゴリズムの最先端研究の世界はどんな感じなのか？ について、その一端をみなさんにも感じていただきたいと思います。

もしかしたら、アルゴリズムのような理論系の研究は、難しくて普通の人間には理解できないというイメージを持っている方もいるかもしれませんが

• 本記事で紹介する研究テーマは説明しやすいものであり
• 一般の IT エンジニア、プログラミングや数学が好きな高校生でも特段の前提知識なしで十分に理解できる

と思いますので、ぜひ気楽に読んでいただければと思います。

目次

章	タイトル
1	研究成果の紹介
2	実世界とかかわるグラフ構造
3	四色定理の歴史
4	"バランス版" 四色定理とアルゴリズム
5	おわりに

1. 研究成果の紹介

本記事では、私が 2026 年 7 月に投稿した論文 The Balanced Four-Color Theorem について紹介させていただきます。米田優峻氏 (@e869120)¹ および指導教員の河原林健一先生 ² との共著論文となります。

Ken-ichi Kawarabayashi, Hirotaka Yoneda, Masataka Yoneda. "The Balanced Four-Color Theorem". To appear at ACM-SIAM Symposium on Discrete Algorithms (SODA 2027). https://arxiv.org/abs/2607.13025

先日、アルゴリズム分野のトップ国際会議 SODA 2027 に採択されました！

四色定理について

みなさんは、四色定理について聞いたことがありますでしょうか？これは、「どんな地図も 4 色あれば塗り分けられる」という定理で、数学の最も有名な結果のひとつです。これを実感するために、みなさんも日本地図が 4 色で塗れるかどうか確かめてみましょう。

（日本地図は、パワポでデザインさんの ウェブページ から頂きました）

答え: 日本地図を 4 色で塗る方法の一例

以下が 4 色で塗る方法の一例です。

補足: なぜ 3 色では塗れないのか？

埼玉・東京・神奈川・山梨・長野・静岡の 6 都県の隣接関係は、以下の図のような、1 県の周りに 5 都県がサイクルのように囲んでいる形になります。

地図を赤・青・緑の 3 色で塗りたい場合、山梨県を赤で塗れば、他の 5 都県を青・緑の 2 色で塗る必要があります。この 5 都県は青と緑を交互で塗る必要がありますが、5 は奇数なので、このようなことは実現できません。これが、どうやっても 4 色必要な理由です。

四色定理は、1976 年（ちょうど 50 年前！）に Appel と Haken によって証明されました。ここまでに至る長くて深い歴史については本記事の 3 章に記します。

しかし、これだけでは足りないと考えました。四色定理によって、地図を 4 色で塗ることはできるけれど、その中でも「都合の良い」塗り方を見つけたい！特に、どのくらい 色のバランスの取れた塗り方 が見つけられるのか、について研究を行いました。

研究成果の紹介

本研究で得られたメインの結果は、厳密に述べると以下のようになります。

本研究の主結果: "バランス版" 四色定理

$n \geq 3$ 頂点の任意の平面グラフについて、どの色も $n/2$ 頂点未満でしか使われないような 4 彩色が必ず存在する。また、このような 4 彩色を計算量 $O(n \log n)$ で求めることができる。

これを地図の言葉で言い直せば、3 個以上の領域からなるどんな地図も、どの色も全体の半分未満の個数の領域でしか使わないように、4 色で塗り分けることができて、このような塗り分け方を高速に求めるアルゴリズムもあります、ということです。

一方で、どんな 4 色の塗り方でも、特定の色を半分ギリギリまで使ってしまうような地図もあります。例えば、以下のような地図を赤・青・緑・黄の 4 色で塗り分けるとして、領域 1 を赤、領域 2 を青で塗ると、その他の領域は緑と黄で交互に塗る必要があるので、1 色が使う領域の数は以下のようになります。

• $n$ が偶数のとき $(n-2)/2$ 個
• $n$ が奇数のとき $(n-1)/2$ 個

したがって、前述の「バランス版四色定理」は、すべての $n \geq 3$ に対して、地図をどの程度バランスよく塗れるかの 完全な限界 を示していることにもなります。³

2. 実世界とかかわるグラフ構造

ここまで地図の話をしていましたが、情報科学では、より一般にモノとモノのつながりを グラフ構造 の形で考えます。地図に限らず、例えば、鉄道路線図、SNS の友人関係、分子の構造、など、たくさんの物事がグラフを使って表されることになります。

グラフ構造の世界では、以下の図のようにモノを 頂点 (vertex)、モノのつながりを 辺 (edge) で単純化して考えます。用途によっては、鉄道路線の例のように、辺に所要時間を表す長さの値が付くなど、追加の情報を組み込むこともあります。

先ほどの 3 つの例をはじめとして色々なものを「グラフ」という抽象的な構造として考えるのが便利なのは、グラフを使うと 2.1, 2.2 節で述べるような様々な問題をコンピューターで解くことができ、それらひとつひとつの問題ごとに、様々な応用を持つからです。

2-1. グラフを使って解く問題

ここでは、グラフがどのような問題に使われるかのイメージを持ってもらうために、3 つの問題を紹介します。

例 1. 最短経路問題

最短経路問題とは、グラフの 2 つの頂点の間の最短経路を求める問題です。例えば、前述の図の鉄道路線の例で、駅 A から駅 F まで行く最短経路は、駅 A → B → C → D → F と行くことで、41 分かかります。

また、みなさんの中にも、鉄道路線の例では路線の乗り換えにかかる時間を考慮できていないのではないか、と気になる方もいるかもしれませんが、乗り換えを考慮した場合でも最短経路問題を使って求めることができます。

補足: どうやって乗り換えを考慮するのか？

同じ駅の間の 2 つの路線の乗り換え時間を考慮したい場合、その 2 つの路線の駅を「別々の駅（= 別々の頂点）」とみなして、その 2 頂点の間に乗り換え時間の長さの辺を追加すればよいです。

先ほどの例で、山手線と中央線の乗り換えに、B 駅で 4 分、D 駅で 8 分かかる場合、以下のグラフでモデル化されます。この場合は、A 駅から F 駅まで行く最短経路は、駅 A → B1 → B2 → E → F と行くことで、47 分かかります。先ほどと異なる経路が最短になっていることが分かるでしょう。

最短経路問題は、頂点が $n$ 個、辺が $m$ 本のグラフに対して、計算量 $O(m \log n)$ で高速に求めるダイクストラ法が知られています。プログラミングが得意な方や、アルゴリズムの授業を受けた方がある人で、ご存知な方もいると思います。

例 2. マッチング問題

マッチング問題は、グラフの辺をどの 2 つも隣り合わないように（= 同じ頂点を占めないように）最大でいくつ選べるかという問題です。イメージとしては、前述の図の友人関係のグラフで、友人どうしで 2 人ペアを組むときに、最大で何ペア作れますか、という問題と同じです。

これは、友人関係の話に限らず、より一般の実用的な場面で使うことができます。例えば、学生が就職活動でいくつかの会社に応募して、それぞれの会社が 1 人の学生しか受け入れられないとき、最大で何人が会社に入れるかどうかはマッチング問題になります。以下の図の例では、6 辺をマッチングさせられるので、就職に失敗する学生をゼロにできます。

マッチング問題は、頂点が $n$ 個、辺が $m$ 本のグラフに対して、計算量 $O(m \sqrt{n})$ で高速に求めるアルゴリズムが知られています。⁴

例 3. グラフ彩色問題

グラフ彩色問題は、グラフの各頂点を、辺でつながったどの 2 頂点の色も異なるように、できるだけ少ない色数で塗ってください、という問題です。例として、以下の 2 つのグラフはそれぞれ何色で塗れるでしょうか？

答え: 何色で塗れるか？

左のグラフは 3 色で、右のグラフは 2 色で塗ることができます。

2-2. グラフ彩色問題について

グラフ彩色問題は、アルゴリズム分野の最先端で特に多く研究されている問題のひとつです。その理由は、最短経路問題やマッチング問題とは異なり、効率的に解くアルゴリズムが知られていない からです。現在知られている最速のアルゴリズムでも計算量 $O(2^n)$ かかります。すなわち、$n = 100$ 頂点のような比較的小さいグラフでも、最適な答えが現実的な計算時間では求まりません。なので、その分まだ分かっていないことも多く、重要な研究対象になっています。⁵

応用的な重要性

他方、グラフ彩色問題も数多くの応用先を持ちます。代表的なものがスケジューリングです。例えば、いくつかの仕事があって、特定の 2 つの仕事は（時間帯が重なるなどの影響で）同じ人に割り当てられないとき、最小人数で全部の仕事を行う方法を見つけたい、という問題を考えます。これは、各仕事を頂点とし、同じ人に割り当てられない 2 つの仕事を辺でつないだグラフについての、グラフ彩色問題になります。

例えば、上図の例では 3 人が最小になります。社員 A に仕事 1, 4 を、社員 B に仕事 3, 6 を、社員 C に仕事 2, 5, 7 をやらせればよいです。

"バランス" の考え方

グラフ彩色の応用例では、単に最適な色の塗り方をひとつ得るだけでなく、その中でも「都合の良いもの」を見つける必要があります。例えば、スケジューリングの問題では、特定の 1 人があまりにもたくさんの仕事をしすぎるのは良くないため、バランスの取れたスケジュール を組むことが重要になります。

すなわち、各色の頂点数にできるだけ差がつかないグラフ彩色、ということです。本記事では "バランス版" 四色定理について解説していますが、応用的な視点でもバランスを考えることが重要であることをお分かりいただければと思います。

3. 四色定理の歴史

この章では、四色定理の歴史と、どのようにして証明されたのかのバックグラウンドを説明します。

四色定理は、先ほど紹介したように「すべての地図は 4 色で塗れる」というものですが、グラフの言葉で表せば、すべての平面グラフは 4 色で塗れる、ということになります。ここで、平面グラフ とは、グラフを辺の交差なく平面上に描けるグラフのことを指します。

このように、2.2 節で紹介したグラフ彩色問題と関連しており、実際には、グラフ彩色問題そのものが、四色問題（19 世紀当時は証明されていなかったので、四色定理とはまだ呼ばれていなかった）をルーツに持っています。

3-1. 四色定理のみなもと

1852 年、イギリス・ロンドン。日本ではまだ江戸時代で鎖国が行われている一方（黒船来航の 1 年前！）、イギリスではまさに産業革命が始まり、世界の覇権を握っていた時代です。

（画像は https://www.thehistoryoflondon.co.uk/in-brief-late-victorian-london/ より）

イギリスの数学者 De Morgan（高校 1 年の数学で習う「ド・モルガンの法則」でおなじみ！）および彼の学生 Guthrie は、イギリスの地図を塗り分けるときに「すべての地図は 4 色で塗り分けられるのではないか？」と気づき、ここで四色問題が生まれました。

3-2. 6 色での塗り方

四色定理は有名で悪名高い定理であるため、とても難しいイメージがありますが、4 色ではなく 6 色使っていいなら、そこまで難しいことはありません。まずはこれを解説します。

Step 1. 平面グラフの辺数

まず、前提として、平面グラフはあまり多くの辺を持つことができません。実際に、頂点数 $n = 3, 4, 5, 6, \dots$ の場合で試してみると、辺をこれ以上追加できなくなるまで追加しても、以下の図のように $3, 6, 9, 12, \dots$ 辺までしか行けません。一般に、平面グラフは最大でも $3n-6$ 辺しか持つことができません。

定理 1. どんな $n \geq 3$ 頂点の平面グラフも、$3n-6$ 本以下の辺を持つ。

最大で $3n-6$ 辺であることの理由（やや難しい）

証明には オイラーの多面体定理 を使います。これは、平面に辺の交差なく描いた連結なグラフに対して、以下の等式が成り立つというものです。

V - E + F = 2

ただし、$V$ は頂点の数、$E$ は辺の数、$F$ は "外側" を含めた面の数（つまり、グラフの内部の面の数に 1 を足したもの）となります。上図の 6 頂点のグラフの例で実際に数えてみると、$V = 6, E = 12, F = 8$ となるので、$V - E + F = 2$ を満たしていることが分かります。

ここで、「辺とそれに接する面」の組の個数 $c$（これは「面とそれが属する辺」の組の個数と同じ！）を、2 通りの方法で数えます。

• すべての辺はちょうど 2 つの面に接します。よって、$c = 2E$ です。
• すべての面は 3 つ以上の辺からなります。よって、$c \geq 3F$ です。

以上より、$3F \leq 2E$ が成り立ちます。これは、$F \leq \frac{2}{3} E$ ということです。よって

2 = V - E + F \leq V - E + \frac{2}{3} E = V - \frac{1}{3} E

となります。$V = n$ なので、$n - \frac{1}{3} E \geq 2$、これを式変形すると、$E \leq 3n-6$ が得られます。

Step 2. 頂点の次数に着目

グラフの頂点につながっている辺の個数を、その頂点の 次数 (degree) といいます。例えば、先ほどの図の 5 頂点 9 辺のグラフでは、次数 3 の頂点が 2 つ、次数 4 の頂点が 3 つあります。グラフの次数には、以下の性質があります。

定理 2. すべての頂点の次数の合計は、辺の数の 2 倍に等しい。

これが成り立つ理由は、頂点 $x, y$ を辺でつなぐことによって、頂点 $x, y$ の次数がそれぞれ 1 ずつ増えるので、言い換えれば「各辺は次数の合計を 2 ずつ増やしている」といえるからです。この性質は、2 つの頂点が握手するイメージで 握手補題 とも呼ばれています。

さて、以上の 2 つの定理を組み合わせてみましょう。

定理 3. どんな平面グラフも、次数 5 以下の頂点が必ず存在する。

$n \leq 2$ の場合は自明なので、$n \geq 3$ とします。まず、定理 1 より、平面グラフは $3n-6$ 辺以下しかないので、定理 2 より、次数の合計は $6n-12$ 以下となります。しかし、仮にすべての頂点の次数が 6 以上であれば、次数の合計は $6n$ 以上となり、矛盾します。だから、次数 5 以下の頂点が必ず存在します。

Step 3. 平面グラフの作り方

さて、平面グラフに次数 5 以下の頂点が必ずあることが分かりました。したがって、次数 5 以下の頂点（およびつながった辺）を削除する、ということを以下の図のように繰り返して、すべての頂点を削除することができます。

（頂点に書かれている数字は、その頂点の次数を表しています）

では、これを逆再生してみましょう！今度は、何もない状態から始めて、新しい頂点を 5 本以下の辺とつないで追加する、ということを繰り返すことで、作りたい平面グラフを必ず作れる、ということになります。

Step 4. ひとつずつ塗ってみよう

このような、新しい頂点を追加していく順番で、色を決めていくことを考えます。

ここで、新しく追加する頂点の次数は 5 以下なので、6 色の中で 1 色は必ず使える色（= 隣接する頂点で使われていない色）が残るから、その中の好きな色を選んで塗れます。これで、どんな平面グラフも 6 色で塗れることがわかりました。

定理 4. どんな平面グラフも 6 色で塗ることができる。

3-3. Kempe の新しいアイデアと "五色定理"

四色問題は、1860 年代以降、数多くの数学者が証明を試みましたが、すべて失敗に終わりました。その中でも、イギリスの数学者 Kempe が 1879 年に思いついた新しいアイデア Kempe Chain によって、平面グラフが 5 色で塗れるという "五色定理" が証明されることになります。

なお、この Kempe Chain のアイデアは、1 世紀後になって四色定理の証明にも使われることになります。

Step 1. 5 色で失敗するケース

まず、先ほど平面グラフを 6 色で塗る方法を解説しましたが、同じ方法を 5 色でやるとどうなるでしょうか？

• 新しい頂点の次数が 4 以下の場合、必ず 5 色の中で使える色が残っている
• 新しい頂点の次数が 5 でも、隣接頂点の色が「色 1, 2, 3, 4, 5 ひとつずつ」でない限りは、5 色の中で使える色が残っている

したがって、5 色で失敗するすべての原因は、以下の図のように隣接頂点の色が「色 1, 2, 3, 4, 5 ひとつずつ」となる特殊なケースにある、といえます。

Step 2. これを回避する "Kempe Chain"

このような状況を打開するために、Kempe は新しいアイデアを思いつきました。これは、色の塗り方を上手く変えることによって、「色 1, 2, 3, 4, 5 ひとつずつ」の状況から脱却する、というものです。

例えば、新しい頂点 X の隣にある色 1 の頂点 Y を色 3 に変えたいとします。しかし、Y が色 3 の頂点 Z に隣接していたら、これはできません。ここで、Z を色 1 に変えて、これが色 1 の頂点 W に隣り合っていたら W を色 3 に変えて、・・・ということを行います。

すなわち、色 1 と色 3 の頂点でひとつながりになっている部分全体について、色 1 と色 3 を交換する、ということを行います。

しかし、この操作を行ったら、以下の図のように、新しい頂点に隣接する色 3 の頂点が色 1 になってしまって、結局状況を打開できない場合があります。

このような場合は、代わりに色 2 と色 4 で同じことをやることを考えます。ここで、新しい頂点に隣接する色 2 の頂点は色 1, 3 の "鎖" (Kempe Chain) に囲まれているので、操作を行って、新しい頂点に隣接する色 4 の頂点が色 2 に変わる、ということはありません（以下の図も参照）。これで、どんな平面グラフも 5 色で塗れることがわかりました。

定理 5. (Kempe 1879) どんな平面グラフも 5 色で塗ることができる。

実際には、Kempe は「これで四色問題を解くことができた」と信じており、周りの数学者にも受け入れられていました。しかし、11 年後の 1890 年になって、数学者 Heawood によって Kempe の証明に誤りが発見され、実際には 5 色までしか解けていないことが明らかになりました。

3-4. 四色定理への道筋

20 世紀に入ってからも数多くの数学者が四色問題に取り組みました。詳細は省きますが、以下のような重要なアイデアが生み出されました。

• 小さなケースに証明を帰着することを可能とする「reducibility」
• グラフ全体の性質をポテンシャルを使って議論する「放電法」

これらのアイデアをもとに、最終的に四色問題を 1976 年に解いたのは、アメリカ・イリノイ大学の数学者 Appel と Haken でした。

定理 6. (Appel & Haken 1976) どんな平面グラフも 4 色で塗ることができる。

しかし、彼らが行ったのは、1000 通り以上の膨大な場合分けを行うコンピュータによる証明 でした。当時はコンピュータが数学者の間ではまだ一般的ではなく、プログラミングの膨大な計算に基づいた証明は、世界全体を驚かせました。一方で、人間がひとつずつ検証することができないほど場合分けが膨大なこと、このような美しい定理なのに証明が "エレガント" ではないこと、などで多くの批判が巻き起こり、数学界を揺るがす議論の的 となりました。

コンピュータによる場合分けに頼らない四色定理の証明は、50 年経った今もまだ発見されていません。

4. "バランス" 版四色定理とアルゴリズム

今回の研究では、50 年前に証明された四色定理に関して、以下の疑問に取り組みました。

自然な疑問: どの程度バランスの良い 4 色での塗り方があるか？

しかし、四色定理の証明は悪名高いほど複雑であり、そもそも四色定理に関連する事実を証明することはとても難しいように思えます。本章では、どのようなアプローチを使って結果を得たかを紹介します。

4-1. 全体の戦略

今回の研究でとった戦略は、四色定理の難解な証明に直接踏み込むのではなく、四色定理をブラックボックスとして使う というものです。具体的には、以下の戦略をとります。

1. 四色定理を使って、平面グラフを 4 色で塗る方法を何でもいいので求める
2. ここから、最大色の頂点数が減っていくように、塗り方を改善していく

ここで、1. に関しては、平面グラフを 4 色で塗る方法を計算量 $O(n \log n)$ で求めるアルゴリズムが、河原林健一教授および彼の指導学生である井上裕太氏、宮下敦行氏をはじめとする 6 人の研究者によって、2026 年 3 月に 論文 が発表されているので、それを直接使うことになります。なお、彼らが行ったブレークスルーに関しては、以下の Quanta Magazine の記事にも掲載されているので、こちらも興味があればぜひお読みください。

Quanta Magazine, "The Four-Color Theorem Gets a Rare New Proof", 2026 年 9 月 10 日
https://www.quantamagazine.org/the-four-color-theorem-gets-a-rare-new-proof-20260910/

4-2. "3 分の 2" の証明

いきなり「どの色も全体の半分未満」の塗り方を求めるのは難しいかもしれませんが、半分ではなく「3 分の 2」であれば比較的簡単です。ですので、まずはこの方法を紹介します。

Step 1. 改善パートをどうするか？

平面グラフを色 1, 色 2, 色 3, 色 4 の 4 色で塗るとして、最も多くの頂点で使われている色が色 1 であるとします。ここで、以下の改善をできなくなるまで繰り返し行うことを考えます。

• 操作: 色 1 の頂点 $v$ をひとつ選び、それを色 1 以外の色（これを色 $i$ とする）に変える。ただし、この操作は $v$ が色 $i$ の頂点に隣接しない場合しか行えない。

重要な観察として、これ以上改善できなくなったグラフでは、すべての色 1 の頂点が色 2, 3, 4 それぞれの頂点と隣接していることになります。

Step 2. 二部グラフの構造に着目！

ここで、前述の観察では、色 1 の頂点と色 2, 3, 4 の頂点の間の関係を考えているので、ここで色 1 の頂点につながった辺だけを残したグラフについて考えます（これをグラフ $H$ とします）。これは以下の図のようになります。

この新しく作ったグラフ $H$ は 二部グラフ になります。ここで、二部グラフとは、頂点を 2 つのグループ A, B に分けるときに、どの辺もグループ A, B の間をつなぐようにできる、というグラフです。

• 具体例として、2.1 節の学生と会社のマッチングのグラフや、男性と女性の間の友人関係を表したグラフは、二部グラフです。
• グラフ $H$ は、色 1 の頂点をグループ A、色 2, 3, 4 の頂点をグループ B とすると、すべての辺がグループ A, B の間をつなぐので、二部グラフです。

ここで、平面二部グラフは、普通の平面グラフよりもさらに少ない辺しか持つことができません。以下の図のように、最大でも $2n-4$ 辺しか持つことができません。この理由は、平面二部グラフでは三角形の面が存在してはならず、各面が 4 頂点以上からなるからです。

定理 7. どんな $n \geq 3$ 頂点の平面二部グラフも、$2n-4$ 本以下の辺を持つ。

最大で $2n-4$ 辺であることの理由（やや難しい）

ここでは、3.2 節で述べた平面グラフが最大で $3n-6$ 辺しか持たないことの説明に沿って、説明を行います。

まず、平面二部グラフは、三角形の面が存在しません。なぜなら、三角形は二部グラフではないからです。したがって、すべての面は 4 つ以上の辺からなるため、（普通の平面グラフで $3F \leq 2E$ なのに対して）$4F \leq 2E$ が成り立ちます。これは、$F \leq \frac{1}{2} E$ ということです。よって

2 = V - E + F \leq V - E + \frac{1}{2} E = V - \frac{1}{2} E

となります。$V = n$ なので、$n - \frac{1}{2} E \geq 2$、これを式変形すると、$E \leq 2n-4$ が得られます。

Step 3. 最後のステップ

では、ここまで準備できたところで、いざ "3 分の 2" の証明を始めましょう！

まず、色 1 の頂点の個数を $k$ とします。これ以上改善の操作が行えない場合、どの色 1 の頂点も色 2, 3, 4 の頂点すべてにつながっているので、グラフ $H$ 上でも次数が 3 以上になります。したがって、グラフ H には辺が $3k$ 本以上あります。

一方、定理 7 より、グラフ $H$ には $2n-4$ 本以下しか辺がありません。よって、$3k \leq 2n-4$ が成立します。式変形をすると、$k \leq \frac{2}{3} n - \frac{4}{3}$ となり、改善ができなくなった状態では色 1 の頂点の個数が全体の 3 分の 2 未満であることが分かります。

定理 8. $n \geq 3$ 頂点の任意の平面グラフについて、どの色も $\frac{2}{3} n - \frac{4}{3}$ 頂点以下でしか使われないような 4 彩色が必ず存在する。

しかし、残念ながらこの方法だと 3 分の 2 が限界になります。以下のようなグラフの塗り方の状態では、色 1 が全体のほとんど 3 分の 2 の頂点を占めますが、どれも他の色に変えることができません。

4-3. Kempe Chain の再登場

ここまでで、色 1 の頂点を他の色に変えることによって改善する、という方法には限界があることが明らかになりました。したがって、よりよい改善の方法を考える必要があります。特に、別の頂点の色を変えることによって色 1 の頂点を他の色に変えられるようにする、ということを行う必要があります。

さて、以下の新しい改善の方法を考えましょう。

• 色 1 と色 $i \ (\neq 1)$ の頂点でひとつながりになっている部分を選ぶ。
• それらの頂点について、色 1 と色 $i$ を交換する。

よく見ると、これは 3.3 節で五色定理を証明するのに使った Kempe Chain のアイデアが、ここで再び登場する形となります。これにちなんで、改善の方法を Kempe Change と呼ぶことにします。

4-4. なぜ改善できるのか？

実は、この方法で改善を繰り返すと、改善できなくなった時にはどの色も全体の半分未満の頂点でしか使われていない状態になることが証明できます。本節ではこの理由を直感的に説明します。

どんなケースで「改善できない」のか？

まず、Kempe Change で改善できない代表的なケースとして、そもそも色 1 と色 $i$ のすべての頂点がひとつながりになっている、という状況があります。その場合は、Kempe Change を行っても、色 1 の頂点がすべて色 $i$ に、色 $i$ の頂点がすべて色 1 になるので、最大色の個数は変わりません。

この状況をもっと数学的に書きます。以下のようにグラフ $H_2, H_3, H_4$ を定義します。

• $H_i \ (i = 2, 3, 4)$: 色 1 と色 $i$ の頂点およびそれらをつなぐ辺からなるグラフ

このとき、$H_2, H_3, H_4$ がすべて 連結⁶ であれば、改善できません、ということです。（以下の図の例では、$H_2, H_3, H_4$ はいずれも連結でなく、Kempe Change による改善を行うことができます）

グラフの連結性

ここで、$k$ 頂点のグラフを連結にするためには、辺が $k-1$ 本以上必要です。この理由は、辺がひとつもない状態ではかたまり（数学的に言えば「連結成分」）が $k$ 個あるが、辺を 1 つ追加することで、2 つのかたまりを 1 つにまとめて、かたまりの個数を 1 つ減らせるからです。連結なグラフはかたまりが 1 つなので、$k-1$ 辺必要です。

定理 9. $k \geq 1$ 頂点の連結なグラフは、$k-1$ 本以上の辺を持つ。

さて、計算してみよう

では、果たしてこのようなケースは色 1 の頂点が何個以上であれば起こり得るのか、実際に計算してみましょう。

• 色 1, 2, 3, 4 の頂点の個数を $c_1, c_2, c_3, c_4$ とします。
• すると、$H_2, H_3, H_4$ の頂点数はそれぞれ $c_1 + c_2, c_1 + c_3, c_1 + c_4$ です。
• ここで、$H_2, H_3, H_4$ は連結なので、定理 9 より、辺数はそれぞれ $c_1 + c_2 - 1, c_1 + c_3 - 1, c_1 + c_4 - 1$ 本以上です。
• グラフ $H$ は、グラフ $H_2, H_3, H_4$ を組み合わせてできるグラフなので、その辺数は $H_2, H_3, H_4$ の辺数の合計になります。よって、$H$ の辺の本数は最低でも:

\begin{align*}
(\text{$H$ の辺数}) \geq \ & (c_1 + c_2 - 1) + (c_1 + c_3 - 1) + (c_1 + c_4 - 1) \\
= \ & 2c_1 + (c_1 + c_2 + c_3 + c_4) - 3 \\
= \ & 2c_1 + n - 3
\end{align*}

• 一方、$H$ は平面二部グラフなので、定理 7 より $2n-4$ 辺以下しかありません。
• 以上より、$2c_1 + n - 3 \leq 2n-4$ が成り立ちます。式変形すると、$c_1 \leq \frac{n-1}{2}$ が得られます。

よって、色 1 が全体の半分以上を占めるときに $H_2, H_3, H_4$ がすべて連結になることは そもそも起こり得ない のである、ということが証明できました。これが、"バランス版" 四色定理が成り立つ直感的な理由になっています。

なお、いずれかが連結でなくても Kempe Change で改善できないケースもありますが、その場合にはまた別の理由で損をすることになります。これは難しいですが、専門的にざっくり説明すると、$H_i \ (i = 2, 3, 4)$ のいずれかの連結成分 $C$ について「色 1 の頂点数が色 $i$ の頂点数以下になる」という逆転現象が生じます。すると、$C$ にサイクルが生じて辺が無駄になるか、$H$ に次数 $1$ の頂点が生じるせいで $H$ 全体に入れられる辺数が減るか、そのどちらか一方の理由で損をしてしまうからです。具体的な証明については、ぜひ論文を参照いただければと思います。

4-5. 高速なアルゴリズム

最後に、十分バランスの取れた 4 色の塗り方をどのくらい速く求められるのか、そのアルゴリズムの計算量について考えます。

まず、1 回の改善で最大色の頂点数を少なくとも 1 ずつ減らすことになるので、多くても $n/2$ 回の改善で最大色の頂点数を $n/2$ 未満にできます。また、1 回の改善は計算量 $O(n)$ で行えます（詳しくは省略しますが、グラフ $H_2, H_3, H_4$ を作ってかたまりを全部求めればよいので、深さ優先探索 (DFS) などを使って実現できます）。よって、全体では計算量 $O(n^2)$ で答えが求まります。

では、さらに高速に答えを求めることはできるのでしょうか？

アイデア: 最大色の頂点が多いほど得をする

重要な点として、最大色の頂点数 $c_1$ が $n/2$ ギリギリの場合でも $H_2, H_3, H_4$ のいずれかは連結になりません。また、$c_1$ が $n/2$ をはるかに超えている場合は、$H_2, H_3, H_4$ が大量のかたまりに分かれていることになります。このような状況では、いくつかのかたまりに対して同時に Kempe Change をすることによって、2 色の頂点数をより均等に近づけることができます。

指数関数的改善

このようなアイデアを使うと、1 回の改善で $c_1 - n/2$ を前の $\frac{3}{4}$ 倍に減らすことができます。すると以下の図のように、2 回で $\frac{9}{16}$ 倍、3 回で $\frac{27}{64}$ 倍、... と 指数関数的に減少 していき、$\log n$ 回程度で最大色の頂点数が $n/2$ 未満になります。

このようにして、塗り方を改善するパートの計算量を $O(n \log n)$ にしています。最初の 4 色の塗り方を求めるのは、4.1 節で述べた通り既存の研究で計算量 $O(n \log n)$ が実現されているので、全体を通しても計算量 $O(n \log n)$ で答えが求まりました。

以上で本研究のメインの結果である "バランス版" 四色定理の紹介を終わります。

5. おわりに

本記事をお読みいただき、ありがとうございました！

これで、アルゴリズム分野の最先端研究がどんなことをやっているか、少しでもイメージがついたらいいなと思います。このような理論的な研究は難しくてやっている内容すら理解できないという先入観を持っていた方もいると思いますが、実際には、"バランス版" 四色定理のような身近に感じられる話題も最先端の理論研究において行われています。

ところで、この「地図を 4 色でどのくらいバランス良く塗れるか？」という疑問はとても自然なものだと思いますが、現実は意外にも、過去の研究者が「未解決問題」として提示したり考えていたわけではありませんでした。⁷

手法や証明はアルゴリズム分野の中でも比較的単純であるため、もし四色定理が解かれた 1980 年頃にこれが未解決問題として挙がっていたら、1990 年頃には解かれていたのではないかと考えています。このような自然な疑問についても、まだ見いだせていない面白い性質やアルゴリズムが隠れているということを実感しました。研究活動は問題を解くだけでなく、そのような問いを見つける部分でも楽しいことである、と思っています。

1. 米田優峻氏 (@e869120) は、Qiita でも レッドコーダーが教える、競プロ・AtCoder上達のガイドライン など数多くのヒット記事を執筆しており、書籍 問題解決のための「アルゴリズム×数学」が基礎からしっかり身につく本、競技プログラミングの鉄則、高校数学の基礎が150分でわかる本 などの著者としても知られています。 ↩

2. 河原林健一教授は、アルゴリズム分野において日本で最も優れた研究者の一人です。最小カット問題の準線形時間アルゴリズム の発見 (2021 年ファルカーソン賞受賞) をはじめとして、数多くのブレークスルーを生み出しています。 ↩

3. この図の例では、$n = 3, 4, 5, 6, 7, 8, 9, 10, \dots$ のときに 1 つの色が 1, 1, 2, 2, 3, 3, 4, 4, ... 個の領域を占めることになります。一方で、バランス版四色定理は、1 つの色を 1, 1, 2, 2, 3, 3, 4, 4, ... 個の領域でしか使わないように 4 色で塗れることを示しています。すなわち、すべての $n \geq 3$ で上界（= アルゴリズムの性能）と下界（= アルゴリズムの限界）が一致する、といえます。 ↩

4. マッチング問題では増加路アルゴリズムが有名ですが、計算量 $O(m \sqrt{n})$ と速いアルゴリズムについては、二部グラフに対しては Hopcroft-Karp のアルゴリズム、一般のグラフに対しては Micali-Vazirani のアルゴリズムが知られています。 ↩

5. グラフ彩色のような効率的に（= 多項式時間で）解けていない問題についても、どのようなグラフなら効率的に解けるのか、あるいは完全な最適な答えでなくてもいいから効率的にある程度良い答えが出せるのか、など色々な研究テーマが考えられます。 ↩

6. グラフが連結であるとは、どの頂点からどの頂点へも辺をたどることによって到達できることです。 ↩

7. 少なくとも、一般の平面グラフがどのくらいバランス良く塗れるのかという問いを考えている論文は、私が調べた限りではひとつもありませんでした。 ↩