1960年代のグラフの難問、ついに決着

いくつかの点をとり、そのうちのいくつかの組を線で結ぶ。数学者はこれをグラフと呼び、点を頂点、線を辺と呼ぶ。閉路(サイクル)とは、異なる頂点を通って出発点に戻る閉じた輪のことだ。自然に浮かぶ疑問は、グラフの辺を、どの辺もちょうど一度ずつ使うようにして、閉路に分けられるかどうかだ。

論文が振り返るように、その答えはずっと前から知られている。それができるのは、どの頂点にも偶数本の辺がつながっているときに限られる。そうしたグラフはオイラーグラフと呼ばれる。次の疑問は、閉路がいくつ必要かだ。そして閉路だけでは済まないグラフについては、単独の辺も部品として認める。

予想

1960年代、エルデシュとガライは、n個の頂点をもつあらゆるグラフの辺は、nに高々比例する個数、つまりO(n)個の閉路と単独の辺に分けられると予想した。エルデシュはこの問題を、自身の未解決問題集のいくつかに収めている。関連するハヨシュ(Hajós)の予想は、どのオイラーグラフも高々(n − 1)/2個の閉路に分けられるかを問う。

望みうる最善は線形だ。エルデシュは、約1.5 n個の部品を必要とするグラフがあることを示した。問題は、nのある定数倍でつねに足りるかどうかだった。

じわじわと進んだ50年

エルデシュとガライ自身が、単純な方法に気づいていた。いちばん長い閉路をくり返し取り除くのだ。これで部品はおよそn log n個になる。論文によれば、これが50年近く、一般のグラフに対する最良の上限であり続けた。最近になって、コンロン(Conlon)、フォックス(Fox)、スダコフ(Sudakov)がこれを n log log n に下げ、続いてブチッチ(Bucić)とモンゴメリー(Montgomery)が n log* n にまで下げた。log* n は、1を下回るまでに対数を何回とらなければならないかという数で、想像を絶するほどゆっくりしか増えない。これらの手法は段階を重ねて進み、各段階でおよそn個の閉路を費やすので、段階の数がつねに最終的な個数に忍び込んできた。この予想は、ランダムグラフのような特別な族についても証明されていた。

輪の代金を払う重み

韓国KAISTの**キム・ジェフン(Jaehoon Kim)**が、ついにこの予想を証明した。ある固定された定数Cがあって、n個の頂点をもつどのグラフも、高々Cn個の閉路と辺に分けられる。その系として、ハヨシュの予想も定数倍の違いを除いて成り立つ。

証明は段階という考え方を捨てる。一つの手続きが閉路と辺を一つずつ取り除き、その総数を二つの量で抑える。どちらの量も、nの定数倍を超えない。

• 次数にもとづくポテンシャル。 各頂点には、つながる辺の数とともに小さくなる重みが与えられる。おおよそ 1 / (次数 × log² 次数) だ。頂点の重みの合計が1以上になる閉路を重い閉路と呼ぶ。重い閉路を一つ取り除くと、全体の「ポテンシャル」が少なくとも1下がる。そしてそのポテンシャルは、はじめはnの定数倍以下しかない。だから重い閉路を取り除けるのはO(n)回まで。
• 頂点の数。 重い閉路が一つも残っていないとき、グラフは「軽い」。主要な新定理は、次数の大きい軽いグラフは、密でほぼ閉じた領域を必ず含むことを示す。その領域は、その大きさに比例する個数の閉路と辺に分けられ、そのあと領域の頂点の少なくとも50分の1は、つながる辺が2本以下になって、永久に脱落する。各頂点が脱落できるのは一度だけなので、この部分の費用もO(n)だ。

グラフの密な部分では、「エクスパンダー」を通るようにつなぐ道を引くことで、道の断片を一つの閉路に閉じる。ランダムな色分けによって、一つの閉路のつなぐ道どうしが離れたままに保たれる。— 図3、Kim (2026), arXiv:2610.07840.

こうした密な領域を分けるために、証明はブチッチとモンゴメリーが用いた頑健な「エクスパンダー」(どの頂点の集合にも多くの隣接頂点があるグラフ)の道具立てを拡張し、さらに頂点をランダムに色分けして、同じ閉路のつなぐ道どうしがけっしてぶつからないようにする。

まだ解かれていないこと

定数Cは途方もなく大きく、著者はそれを最適化しようとはしていない。最良の定数(少なくとも1.5)を見つけることは未解決のままだ。厳密な形のハヨシュ予想や、グラフを道に分けることについてのガライの関連予想も同様だ。重みづけの技法に必要なのは、和が収束する重みだけなので、著者はほかの分解問題にも使えるかもしれないと述べている。

これは単著のプレプリントで、まだ査読による確認を受けていない。

利益相反。 著者は、議論を練り上げ、文章と図を準備するにあたって、ChatGPT(OpenAI)とClaude(Anthropic)を幅広く使ったこと、そしてすべての結果を自ら検証し、論文に全面的な責任を負うことを述べている。いまあなたが読んでいるこの文章も、Claudeが書いたものだ。