ネットワークの上限、ついにあらゆる大きさで証明される
いくつかの点を取り、そのうちのいくつかの組を線で結ぶ。数学者はこれをグラフと呼ぶ。点はその頂点、線はその辺であり、2つの頂点の間の距離とは、一方から他方へたどるのに必要な辺の最小本数のことだ。ここで2つの規則を加える。どの頂点の組も、距離が2以下でなければならない。つまり、直接結ばれているか、共通の隣人を介してつながっているかのどちらかだ。そして、余分な辺があってはならない。どれか1本でも辺を取り除くと、ある組が2歩より遠く離れてしまう。このようなグラフを直径2臨界グラフ（diameter-2-critical graph）と呼ぶ。このグラフは、辺を何本まで持てるだろうか。
Mantelの上限と、より大胆な予想
1907年、Mantelは、三角形（互いにすべて結ばれた3つの頂点）を含まないn頂点のグラフは、辺を高々**⌊n²/4⌋本**しか持たないことを証明した。nの2乗を4で割り、整数に切り下げた数だ。この上限に達するグラフは1つしかない。均衡完全二部グラフ（balanced complete bipartite graph）である。できるだけ同じ大きさの2つのグループからなり、一方のどの頂点も他方のすべての頂点と結ばれ、グループの内部には辺がない。
三角形を含まないグラフのうち、三角形を作らずにはもう1本も辺を加えられないものは、すべて直径2臨界グラフである。逆は成り立たない。三角形を含む直径2臨界グラフも存在するからだ。
頂点7個、辺9本の直径2臨界グラフで、三角形v1v3v5を含む。v1v3を取り除くと、v2とv3を結ぶ唯一の2歩の経路が失われる。三角形の外にある辺を取り除くと、その両端を結ぶ2歩の経路がなくなる。— Figure 1, Das & Fox (2026), arXiv:2610.39032.
予想の中身は、三角形があっても何も得をしない、というものだった。n頂点の直径2臨界グラフでも辺は高々⌊n²/4⌋本であり、それに達するのはやはり均衡完全二部グラフだけだ、と。Mantelの定理はその特別な場合として導かれることになる。図の7頂点の場合、上限は辺12本である。
2の塔
Zoltán Fürediが伝えるErdősの話によれば、この問題は1960年代のOreの研究にさかのぼる。Ján Plesníkは1975年に、辺の数の上限を予想として述べた。MurtyとSimonは独立にこれを提案し、極値をとるのは均衡完全二部グラフだけだと付け加えた。これがMurty–Simon予想の名の由来である。1970年代から1980年代にかけて、c·n²の形の上限が少しずつ下がり、cは1/4にどんどん近づいていった。
1992年、Fürediは、十分に大きなすべてのnについてこの予想を証明した。用いたのは正則性の手法（regularity methods）、すなわちSzemerédiの正則性補題から派生した道具である。代償は、出発点となる大きさだった。nは少なくとも高さ約10¹⁴の2の塔でなければならなかったのだ。つまり、2の肩に2を乗せ、その肩にまた2を乗せ……と続けて、約10¹⁴個の2を積み重ねた数である。計算は上から下へ進める。どの2も、その上に積まれたもの全体を指数としてべき乗される。それより小さい大きさでは、決着がついていたのは特殊なグラフの族だけだった。
辺と、結ばれていない組
スタンフォード大学数学科のSanjana DasとJacob Foxによる新しい証明は、3以上のすべてのnで成り立つ。用いるのは極大マッチング（maximal matching）だ。どの2本も頂点を共有しない辺の集まりで、さらに辺を1本加えようとすると、必ずどれか2本が出会ってしまうもののことである。n頂点上のマッチングは、辺を高々⌊n/2⌋本しか含まない。
鍵となる補題はこうだ。直径2臨界グラフでは、どの極大マッチングについても、マッチングに含まれない辺の数が、非辺（non-edge）、つまり結ばれていない頂点の組の数を上回ることは決してない。あとは算術である。辺の数の2倍は、頂点の組の数とマッチングの大きさの和以下になる。頂点が10個なら、組は45個、マッチングの辺は高々5本で、合わせて50。よって辺は高々25本だ。どのnについても、この和はちょうどMantelの上限の2倍になる。
補題そのものは、注意深い帳簿づけである。非辺は、その両端を結ぶ2歩の経路がただ1つしかないとき、臨界的（critical）であるという。図1の12個の非辺はすべてそうだ。著者らは、各臨界非辺をその経路の2本の辺に結びつけ、こうしてできた網を連結な部分に分ける。1つの部分が含む辺の数は、臨界非辺の数より多くても1つだけであり、その余剰をもつ部分はそれぞれ、臨界的でない非辺によって埋め合わされなければならない。それを見つけるために、著者らはスイッチ出口（switch exits）を使う。部分に属する辺または臨界非辺を1つ取り、その一方の端を、マッチングにおけるその端の相方と入れ替えるのだ。臨界的でない非辺はそれぞれ高々2回しか割り当てを求められず、余剰をもつ部分はそれぞれ少なくとも2回割り当てを求める。こうして勘定が合う。
誰が何を見つけたか
「この証明は大部分がAI、具体的には2026年8月11日のGPT-5.6 Solによって見つけられた」と、著者らは短いAI声明に書いている。モデルは⌊n²/4⌋という上限の完全な証明を見つけ、著者らはそれを簡潔にした。頂点の数が偶数の場合については、モデルは均衡完全二部グラフが唯一の極値であることも証明した。その際に頼ったのは、すべての極大マッチングが完全（perfect）、つまりすべての頂点を覆うようなグラフについて、Sumnerが証明した事実である。
頂点の数が奇数のときは、完全マッチングは存在しない。そして多くのグラフでは、すべての極大マッチングがちょうど1つの頂点を取りこぼす。モデルの論証は、この場合に合わせて修正することができなかった。著者らは、すべてのnで成り立つ、等号の場合の別の証明を見つけ、論文は自分たちで書いた。最後にGPT-6 Astraに通したところ、「いくつかの小さな修正」につながった。この論文はプレプリントで、まだ査読を受けておらず、論証をコンピュータで検証した版についての言及もない。
1907年へ戻る
あるグラフが上限に並ぶなら、鍵となる不等式はすべての極大マッチングについて等式になる。マッチングを巧みに選ぶことで、著者らは、そのようなグラフは星グラフ（star）、つまり1つの頂点が他のすべての頂点と結ばれ、それ以外に辺がないものであるか、臨界非辺をまったく持たないかのどちらかであることを示す。直径2臨界グラフでは、三角形のどの辺もいずれかの臨界経路の上にあるので、臨界非辺がないということは三角形がないということだ。星グラフにも三角形はない。したがって、上限に並ぶグラフは三角形を含まない。そして最後の一歩は、この予想がもともと強めようとしていた定理、すなわち1907年のMantelの結果である。それによって、上限にただ1つ残るのは均衡完全二部グラフとなる。