ロヴァース予想 — 例外は 4 個。5 個目の探索空間は欠損 def で三つに割れる
ハミルトン閉路を持たない連結頂点推移グラフは、K₂ を除いて 4 個しか知られていません。4 個とも「閉路は無いが路はある」——だから路の予想はまだ倒れていません。この記事は、その 4 個を構成して確かめ、ケイリー版を 9,805 個掃き、ペテルセンとコクセターの真上の段に閉路を構成したうえで、5 個目がいるとすればどこかを欠損 def = |V| − 最長閉路長 で三つの箱に分けます。
Lean機械検査済み（Lean 4 + mathlib、標準三公理以下、sorryAx・native_decide なし。定理名を添える）
紙証明はあるが機械検査は未了
計算この端末で確かめた範囲。外に出す主張にはしない
既知言い換え・既知の定理・外の文献の確認
- この問題は何か
- 世界はどこまで来ているか — 例外は 4 個・三価は 1,280 頂点まで全数検査済み
- やったこと ①：4 つの例外を構成して確かめる
- やったこと ②：ケイリー版を 9,805 個掃く
- やったこと ③：ペテルセンとコクセターの「上の段」に閉路を二つ
- 5 個目はどこにいるか — 欠損 def で三つの箱
- 残ったこと
- 出典と再現
この問題は何か
1970 年の問いです。
連結な頂点推移グラフは、ハミルトン路を持つか。
（頂点推移＝どの頂点も対称に見える。ハミルトン路＝全頂点をちょうど一度ずつ通る道）
いまも未解決です。そしてこの予想が 56 年生き延びている理由は、たった 4 個のグラフの中に入っています。
世界はどこまで来ているか
| 問い | 状態 |
|---|---|
| 連結な頂点推移グラフはハミルトン路を持つか | 未解決（1970 年から） |
| 連結な頂点推移グラフはハミルトン閉路を持つか | 偽。例外が 4 個知られている（K₂ を数えれば 5） |
| ケイリーグラフはハミルトン閉路を持つか（|G| > 2） | 未解決。反例は一つも見つかっていない |
| 既知の例外 | ペテルセン／コクセター／それぞれの切頭（と K₂） |
| 三価の頂点推移グラフ | 1,280 頂点までの 111,360 個が全数検査済み。例外はちょうど既知の 4 個（Potočnik–Spiga–Verret）既知 |
| 頂点推移グラフ全体の目録 | 47 頂点まで（arXiv:1811.09015）既知 |
| 群の位数が p²・p³・p⁴・2p² | 例外なし（Du–Kutnar–Marušič）。2pq の一般の場合は未解決 |
| 稠密な場合 | 解決済み（Christofides–Hladký–Máthé）。⟹ 5 個目があれば疎 |
この問題の特徴は、例外がこれだけ少ないことです。そしてその 4 個が全部「閉路は無いが路はある」——だから路の予想はまだ倒れていない。5 個目があるなら、少なくとも三価では 1,280 頂点より上で、疎なグラフです。
やったこと ① — 4 つの例外を構成して確かめる
ハミルトン閉路（始点に戻る）を持たない連結頂点推移グラフのうち、K₂（辺一本）を除く 4 個を構成して、機械で確かめました。計算
| グラフ | 頂点 | 辺 | 次数 | 内周 | |Aut| | 頂点推移 | ハミルトン閉路 | ハミルトン路 | def |
|---|---|---|---|---|---|---|---|---|---|
| ペテルセン | 10 | 15 | 3 | 5 | 120 | True | False | True | 1 |
| コクセター | 28 | 42 | 3 | 7 | 336 | True | False | True | 1 |
| ペテルセンの切頭 | 30 | 45 | 3 | 3 | 120 | True | False | True | 3 |
| コクセターの切頭 | 84 | 126 | 3 | 3 | 336 | True | False | True | 3 |
最後の列の def は欠損 |V| − 最長閉路長（§06）。コクセターの最長閉路は 27 で、hypohamiltonian なら |V| − 1 が強制されます。
4 個とも「閉路は無いが、路はある」。
これが予想がまだ生きている理由の実体です。閉路の予想なら、とっくに反例が出ている。路の予想は、まだ倒れていない。
|Aut| の列は、4 個が本当は 2 個であることを見せています。切頭を取っても自己同型群は変わらず（120・336 がそのまま並ぶ）、頂点数も 30 = 3×10、84 = 3×28 と 3 倍になるだけです。⟹ 既知の例外は「原始的な 2 個 ＋ その切頭 2 個」であって、本質的には 2 個です。そして切頭は一段で止まります（§06）。
いちばん小さい例——ペテルセングラフで、それを見てください。
この道は 0 → 1 → 2 → 3 → 4 → 9 → 6 → 8 → 5 → 7。10 頂点を一度ずつ通っています。しかし最後の 7 から最初の 0 に戻る辺がありません。他のどの道でも同じで、閉じられないことが確かめられます。
やったこと ② — ケイリー版を 9,805 個掃く
予想には、より強い形があります。
ケイリー版（未解決）：|G| > 2 の有限群の連結なケイリーグラフは、ハミルトン閉路を持つ。
こちらは閉路です。反例が一つでもあれば大事件。生成系の大きさ 2 まで、作れるだけ作って、全部確かめました。計算
| 族 | 群の数 | ケイリーグラフ | ハミルトン閉路なし |
|---|---|---|---|
| 巡回群 Z₃〜Z₃₀ | 28 | 3,748 | 0 |
| 二面体群 D₃〜D₁₅ | 13 | 1,320 | 0 |
| 対称群 S₃, S₄, S₅ | 3 | 3,537 | 0 |
| 交代群 A₄, A₅ | 2 | 1,188 | 0 |
| 四元数群 Q₈ | 1 | 12 | 0 |
| 合計 | 47 | 9,805 | 0 |
いちばん重かったのは S₅（位数 120、3,420 個、559 秒）、次が A₅（位数 60、1,140 個、138 秒）です。
群は、作った位数を期待値と突き合わせてから使います。生成元の取り方を誤ると、名前は A₅ でも中身が A₄（位数 12）になることがあります——二つの 3-巡回が同じ点を固定していれば、生成されるのはその点の固定部分群です。だから掃きに入る前に、すべての群について assert len(G) == 期待される位数 を通します。An は n が奇数なら 3-巡回と n-巡回で生成されます。
道具の選び方で、桁が変わる
頂点推移性は「全同型を列挙」ではなく距離分割で枝刈りする後戻り探索で、ハミルトン性は「位置変数＋許容組」で組み立て直すのではなく CP-SAT の巡回制約そのもの（AddCircuit）で判定します。570 秒で終わらなかったものが 2.3 秒になりました。「ハミルトン閉路がある」は、ソルバに直接ある制約です。
この掃きが何の検定なのかを分けておきます。9,805 個のケイリーグラフを掃く作業は、より強い「ケイリー版予想」の検定です。既知の 4 個はケイリーグラフではないので、ケイリーグラフをいくら掃いても、5 個目はそこから出てきません。5 個目の探し方は §06 にあります。
やったこと ③ — ペテルセンとコクセターの「上の段」に閉路を二つ
ペテルセングラフ（10 頂点）とコクセターグラフ（28 頂点）は、じつは行列から作れるグラフの族の、最初の段です。F₄ 上の可逆エルミート行列を頂点にして、差の階数が 1 なら辺で結ぶと HGLn(F₄) という族ができ、n = 2 がペテルセン。F₂ 上の可逆対称行列で同じことをすると SGLn(F₂) で、n = 3 がコクセター。Orel（2015）は「この族の上の段はハミルトン閉路を持つか」を未解決問題として立て、280・448・13,888 頂点の三つの場合には Concorde TSP ソルバで閉路を見つけ、一般の場合を未解決のまま残しました。
その次の段、二つに閉路を構成しました。計算
| グラフ | 頂点数 | 頂点推移 | ハミルトン閉路 |
|---|---|---|---|
| HGL₂(F₄) ＝ ペテルセン | 10 | ○ | 無い（古典） |
| SGL₃(F₂) ＝ コクセター | 28 | ○ | 無い（古典） |
| HGL₃(F₄)／SGL₄(F₂)／SGL₅(F₂) | 280／448／13,888 | ○／×／○ | ある（Orel 2015） |
| HGL₄(F₄) | 38,080 | ○ | ある（この端末） |
| SGL₆(F₂) | 888,832 | × | ある（この端末） |
| HGL₅(F₄)／SGL₇(F₂) | 18,887,680／112,881,664 | ○ | 未決 |
方法は Pósa の回転と拡張——路の端が伸ばせなくなったら端の近傍で路を反転する、古い発見的手法です。頂点を行列のビット列に符号化すると隣接が XOR だけで出るので、隣接表を持たずに走れます。38,080 頂点は 0.8 秒、888,832 頂点は約 17 分でした。閉路そのものと、標準ライブラリだけで走る検証器はここで配布しています（検査は 1.4 秒と 35.5 秒で、判定は別経路の実装でも再現しています）。
言えないこと。発見的手法は「ある」しか言えません。どのグラフについても、「無い」かどうかはここでは何も決まっていません。一般の n に対する構成法も与えていません。各族に一つずつ、肯定側の点が付いただけです。それから、既知でないとは書きません。探した範囲——五つの検索語による一般の検索と、Orel 2015 を引いている 6 本の全件——にはこの二つのハミルトン性を書いた文献は見当たりませんでしたが、MathSciNet・zbMATH・会議録の目次・非英語の文献は当たっていません。
この記事の問いとの関係。5 個目の例外は「連結で頂点推移で、ハミルトン閉路を持たない」グラフです。HGL₄(F₄) は頂点推移なので候補の一つでしたが、閉路が見つかったので候補から外れました。SGL₆(F₂) は頂点推移でないので、もともと候補ではありません。つまりこの二つは、5 個目を見つけたのではなく、ペテルセンとコクセターの真上の段には 5 個目がいないことを確かめたものです。
5 個目はどこにいるか — 欠損 def で三つの箱
「ハミルトン閉路があるか」は 0/1 の粗い量です。最長閉路の長さで測り直すと、数になります。
この量には perimeter gap という名があり（Alspach 1981）、頂点推移グラフでは def = 1 ⟺ hypohamiltonian です（長さ |V| − 1 の閉路が外す一点を、頂点推移性でどの点にも移せるから）。既知の 4 個の def は 1, 1, 3, 3。探索空間はこの数で三つに割れます。
| 箱 | 条件 | 既知の住人 | 現状 |
|---|---|---|---|
| I | def = 1（hypohamiltonian） | ペテルセン・コクセター | 三価は 1,280 頂点まで全数検査済み既知 |
| II | 切頭型。def ≡ 0 (mod 3) | 二つの切頭（def = 3） | 3,840 頂点まで空——切頭 T(H) は 3|V(H)| 頂点で、H がハミルトンなら T(H) もハミルトン（補題：circ(T(H)) = 3·circ(H)）紙 |
| III | def ≥ 2 で切頭でない | 例なし | 頂点推移グラフの例は一つも知られていない |
切頭作用素は一世代で凍結します。T(G) が頂点推移になるのは G が弧推移のときで、T(G) 自身は辺推移でないので T²(G) は頂点推移になりません。しかも T(G) がハミルトン ⟺ G がハミルトン。紙 だから箱 II の住人は「ペテルセン・コクセター以外の、ハミルトン閉路を持たない三価の弧推移グラフ」の切頭に限られ、その目録（Foster census）は既刊です。残るのは箱 III です。
箱 III の先頭にあるもの — def = 2 の予想
予想（B135′）。def = 2 の連結頂点推移グラフは存在しない。
この言明は 5 個目そのものより小さく、しかし易しくはありません。Grünbaum は 1974 年に「circ = n − k で、位数 n − k の誘導部分グラフが全部ハミルトンなグラフは k ≥ 2 で存在しない」と予想しており、B135′ はその頂点推移版を含みます。既知 さらに、正則な二部グラフは全閉路が偶なので def が偶——二部では def = 1 は原理的に不可能で、切頭は三角形を持つので二部でない。⟹ 非ハミルトンな二部頂点推移グラフは、あれば必ず箱 III に入り、その最小事例が B135′ の先頭です。紙
頂点推移を外せば、def = 2 はある
Tutte 予想の反例として知られる三価二部グラフ——Ellingham–Horton 54・78、Horton 96——は全部 def = 2 です（周長 52・76・94）。計算 では def = 2 の三価二部グラフはどこまで小さくなれるか。
LeanShiori1161.G30_def2・Shiori1193.G30b_def2・Shiori1193.G30c_def2 — 三つとも同じ形の言明：(∀ v, G.degree v = 3) ∧ G.Colorable 2 ∧ G.Connected ∧ (∃ c : G.Walk 0 0, c.IsCycle ∧ c.length = 28) ∧ (∀ v (c : G.Walk v v), c.IsCycle → c.length ≤ 28) ∧ ¬ G.IsHamiltonian。非ハミルトン性は探索を核の中で走らせて閉じています（外部の証明書なし）。28 頂点以下に無いこと、30 頂点でちょうど 3 類であることは、この端末の全数列挙です——仮定なし（3-連結性・対称性・内周を課さない）、二経路で一致。計算 Ellingham–Horton 54 より 24 頂点小さく、既知の例と違って 3-連結ではありません。
同じ機械で、def = 2 でなくてよければ 20 頂点に非ハミルトンな三価二部グラフがあります（周長 14）。LeanShiori1193.G20_def6 18 頂点以下に無いことと一意性は計算です。計算
次数を上げると空になります。四価二部で def = 2 は n ≤ 24 に無い——全数、対称性の仮定なし。計算 これは Häggkvist 1976 の予想（2-連結 k-正則二部で n ≤ 6k ならハミルトン）の k = 4 の最小域にあたり、そこで「def = 2 の反例」は消えています。対称性を一段だけ課すと紙で下から押さえられます：semisymmetric（正則・辺推移・非頂点推移）で def = 2 なら、三価は n ≥ 50、四価は n ≥ 26。紙 要は「連結・d-正則・辺推移なら辺連結度が d」で、2-辺切断による分解が辺推移性の下で閉じます。
数え上げの定理 — GP(n,3) のハミルトン閉路
一般化ペテルセングラフ GP(n,3)（外輪の n-閉路・歩幅 3 の内輪・n 本のスポーク）について：
定理。n が奇数で n ≥ 7 なら、GP(n,3) のハミルトン閉路の個数（辺集合として数える）は n で割り切れる。
LeanShiori1202.gp3_dvd_hc_odd（標準三公理以下・sorry 0）。n = 7, 9, 11, 13, 15 の個数は 7, 9, 11, 26, 75 で、これも Lean です（Shiori1168.GP7_hc_card … GP15_hc_card）。証明の骨子は、回転 ρ の作用が自由であること——ρj で不変なハミルトン閉路があれば商グラフに巻き数 0 の 2 因子が落ち、窓の勘定と置換の符号で矛盾する——から Burnside で n ∣ #HC。この量は自己同型で不変なので、非ハミルトン性の証明には使えません。探した範囲では活字に見当たりません（OEIS に個数の列は無く、arXiv:2503.08326 は線形漸化式で値を与えますが分類ではありません）。
def = 2 の三価二部グラフの最小位数と、GP(n,3) の定理は、それぞれ短い論文の形で別に置きます。準備中
残ったこと
動いた宿題の現在地は 残っていること にある。ここには現時点の未決だけを置く。
| 内容 | |
|---|---|
| 言えた | 47 群・9,805 個のケイリーグラフに、ハミルトン閉路を持たないものは無い計算 |
| 言えた | 既知の 4 つの例外は、すべて「閉路は無いが路はある」。本質的には 2 つで、切頭は一世代で凍結する紙 |
| 言えた | HGL₄(F₄)・SGL₆(F₂) にハミルトン閉路がある計算（証明書を配布） |
| 言えた | def = 2 の三価二部グラフが 30 頂点にあるLean・28 頂点以下に無い計算／奇数 n ≥ 7 で n ∣ #HC(GP(n,3))Lean |
| 言えない | 予想そのもの。掃きは反例を探す作業であって、無いことの証明ではない |
| 言えない | 生成系の大きさ 3 以上（2 までしか調べていない）・位数 130 以上の群（A₆ は飛ばした）。どちらもケイリー版の検定であって、5 個目の探索ではない |
現時点の未決
| 未決 | どこで止まっているか |
|---|---|
| B135′（def = 2 の連結頂点推移グラフの非存在） | 紙では、三価で内周 ≥ 4 が強制されることと、反例の三つの機構（独立集合の過剰・両側に閉路を持つ 3-辺切断・部分切頭）がそれぞれ別の定理で頂点推移性に潰されることまで。不可能とは決められていない。四価二部の n = 26 は未実行 |
| 箱 III の空 | 頂点推移で def ≥ 2・切頭でないグラフの有無そのもの。三価に限れば 1,280 頂点より上にしかいない |
| 最小性の Lean 化 | 「def = 2 の三価二部グラフは 28 頂点以下に無い」の全数列挙を核に載せると、節点数から見てメモリで決まる（推定 150 GiB）。列挙の構造を変える必要がある |
出典と再現
| もの | 種別 | 出典・道具 |
|---|---|---|
| ロヴァース予想（1970） | 予想 | 頂点推移グラフはハミルトン路を持つか |
| ハミルトン閉路を持たない例外 4 個（と K₂） | 既知 | ペテルセン／コクセター／それぞれの切頭 |
| 4 つの例外の構成と検証 | この端末で計算 | コクセターは指紋（28 頂点・3 正則・内周 7・頂点推移・非ハミルトン）で照合 |
| ペテルセンのハミルトン路 | この端末で計算 | 0→1→2→3→4→9→6→8→5→7 |
| ケイリーグラフ 9,805 個の掃き | この端末で計算 | CP-SAT の AddCircuit。841 秒。全群で位数の表明を通してから掃きに入る |
| 三価の頂点推移グラフ 111,360 個（1,280 頂点まで）の全数検査 | 文献 | Potočnik–Spiga–Verret, arXiv:1201.5317 |
| 頂点推移グラフの完全な目録（47 頂点まで） | 文献 | arXiv:1811.09015 |
| 位数の族ごとの分類（p²・p³・p⁴・2p² には例外なし） | 定理 | Du–Kutnar–Marušič, Combinatorica 41 |
| 稠密な場合の解決 | 定理 | Christofides–Hladký–Máthé, arXiv:1008.2193 |
| 切頭の三定理と Foster census | 既知 | T(G) のハミルトン閉路 ⟺ G のそれ／Aut(T(G)) ≅ Aut(G)／T(G) 頂点推移 ⟺ G 弧推移 |
| Orel の族（HGLₙ(F₄)・SGLₙ(F₂)）と未解決問題 16 | 文献 | Orel, Electron. J. Combin. 22 (2015) |
| HGL₄(F₄)・SGL₆(F₂) のハミルトン閉路 | この端末で計算 | Pósa の回転＋拡張。閉路と標準ライブラリだけの検証器を配布（別経路の実装で再現） |
| perimeter gap の名と問い | 文献 | Alspach 1981 |
| Grünbaum の予想（circ = n − k の一様な族は k ≥ 2 で空） | 文献 | Grünbaum 1974（arXiv:2602.19669 の要旨経由） |
| circ(T(H)) = 3·circ(H)・切頭の凍結 | 紙 | 初等。既刊の可能性が高い |
| Ellingham–Horton 54・78、Horton 96 の def = 2 | この端末で計算 | 最長閉路を SAT で。周長 52・76・94 |
| def = 2 の三価二部グラフ：30 頂点に 3 類 | 機械検査 | Shiori1161.G30_def2・Shiori1193.G30b_def2・G30c_def2。公理は Lean 検証一式 の台帳 |
| 28 頂点以下に無い・30 頂点でちょうど 3 類 | この端末で計算 | 弦図の全数列挙（仮定なし）と、2-辺切断による分解の二経路。3-連結の最小位数 50 は Brinkmann–Zamfirescu, arXiv:2101.00943 |
| 20 頂点の非ハミルトン三価二部グラフ | 機械検査／計算 | Shiori1193.G20_def6。最小性と一意性はこの端末で計算 |
| 四価二部で def = 2 は n ≤ 24 に無い | この端末で計算 | 全数。Häggkvist 1976 の予想は Jackson–Li, JCTB 62 (1994) 経由 |
| semisymmetric で def = 2 なら三価 n ≥ 50・四価 n ≥ 26 | 紙 | 辺推移 ⟹ 辺連結度 = 次数。三価の場合は arXiv:2602.14388（3,000 頂点未満の三価 semisymmetric はハミルトン）に含まれる |
| n 奇 ⟹ n ∣ #HC(GP(n,3))・n = 7〜15 の個数 | 機械検査 | Shiori1202.gp3_dvd_hc_odd・Shiori1168.GP{7,9,11,13,15}_hc_card。公理は Lean 検証一式 の台帳 |
§05 の閉路と §06 の二つの定理のほかに、この記事に新しい数学はありません。4 つの例外も、ケイリー版の予想も、三箱の材料（切頭の定理・Grünbaum の予想・二部の偶奇）も既知です。新しさは「探した範囲で見当たらない」までしか書きません。
予想が生きている理由は、4 個の例外の中身にそのまま入っています。どれも閉路は持たないが、路は持つ。ぎりぎりで生き延びているという形は、リーマン予想やコラッツ予想に現れる「臨界」と同じです。