Yamagishi Complexity Torus Lab | 山岸勇輝ラボ

要旨

一筆書きと巡回路は、どちらもグラフを一周する問題だと思われている。本稿が示すのは、同じ辺を一本足すと、片方だけが壊れることである。片方には頂点ごとの証書があり、片方には無い。新しい定理も法則も主張しない。

第一に、輪グラフの全走査の本数は $(n-1)!$ に一致し、$n=10$ で $\mathbf{362880}$ 本である（第2節）。

第二に、有効なハミルトン閉路はどの $n$ でもちょうど $\mathbf{2}$ 本（往路と復路）である（第2節）。

第三に、$n$ を $1$ 増やすと走査が $\mathbf{8.0000}$ 倍、次は $\mathbf{9.0000}$ 倍と、増え方自体が増える（第2節）。

第四に、$n=20$ では次数 $\mathbf{20}$ 個 対 $\mathbf{1.216451\times10^{17}}$ 本、比は $\mathbf{6.082\times10^{15}}$ 倍である。$n=10$ ではまだ $3.629\times10^{4}$ 倍にすぎない（第3節）。

第五に、これが本稿の芯である。弦を一本足すとオイラー回路は消えるが、ハミルトン閉路は $\mathbf{2}$ 本のままである（第4節）。

第六に、分離子は「頂点ごとの証書があるか」である（第5節）。

キーワード：オイラー路、ハミルトン閉路、NP 完全、グラフ理論、局所的な証明書。

射程（何を示さないか）

新しい定理も法則も主張しない。オイラーの定理も、ハミルトン閉路問題が NP 完全であることも標準的である。計算量理論を作らない。NP 完全性の証明や P と NP の関係には立ち入らない。総当たりの規模だけを数える。よいアルゴリズムを扱わない。分枝限定法や動的計画法は使っていない。総当たりの本数は上限であって、実際に必要な手間ではない。小さなグラフしか走査していない。全走査は $n=10$ までで、$n=20$ の値は $(n-1)!$ から計算した。連結性を判定に含めていない。オイラーの条件のうち「連結」の部分は、輪グラフでは自明なので次数だけを見た。既刊との関係：論文348 は同じグラフで繋ぐのは安く並べるのは高いと示し、分離子を「順序を要求するか」に置いた。本稿の分離子はそれとは別で、「頂点ごとの証書があるか」である。論文300 は同根か別根かが判定できると示した。二つの周回は別根である。論文481 は分離子が無いと反証の行き先が決まらないと示した。本稿はその分離子を一本書く。論文507 は答が接するところで決まる三つを並べた。同じく、似た形の問いが別の型を持つ場合である。加えたのは、全走査の本数が $(n-1)!$ に一致することを確かめたこと、有効な閉路が $2$ 本だと数えたこと、増え方が $8.0000$ から $9.0000$ へ動くことを示したこと、手間の比を $n=10$ と $n=20$ で並べたこと、弦一本で片方だけが壊れることを実測したことである。

1. 記法と問い

設定：頂点 $n$ 個の輪グラフを取り、二つの問いを立てる。一つは「すべての辺をちょうど一度ずつ通る閉路があるか」（オイラー回路）、もう一つは「すべての頂点をちょうど一度ずつ通る閉路があるか」（ハミルトン閉路）である。前者は各頂点の次数が偶数かを見れば足りる。後者は、頂点の並びを総当たりする。以下、全走査の本数と、有効な閉路の本数を分けて数える。

観察 1.1　一筆書きと巡回路は、どちらもグラフを一周する問題だと思われている。辺を尽くすか、頂点を尽くすか、似た形の問いに見える、という像である。

観察 1.2　だが片方は頂点ごとに答が読める。次数が偶数か、もう片方には、そういう読み方が知られていない。

問い：その差は、どこで測れるのか。

2. 全走査を数える

計算 2.1：輪グラフで、二つの判定にかかる手間を数える。

観察 2.2　全走査の本数が $(n-1)!$ に一致する。$362880$ 対 $362880$、閉じた式との一致であり、走査が本当に全部を見ていることの確認になる。

観察 2.3　有効な閉路はどの $n$ でも $2$ 本である。往路と復路、輪グラフには周り方が二通りしかない。

観察 2.4　答が $2$ 本しかないのに、$362880$ 本を調べている。$18$ 万分の $1$ 未満、見つけるのが難しいのではなく、無いことを確かめるのが高い。

観察 2.5　増え方自体が増える。$n$ を $8$ から $9$ にすると $8.0000$ 倍、$9$ から $10$ にすると $9.0000$ 倍、指数なら比が一定になるはずで、そうならない。階乗である。

3. $n=20$ で測る

計算 3.1：$n=20$ で二つの手間を並べる。

観察 3.2　オイラー判定は $n=20$ でも即座に終わる。$0.000000$ 秒、頂点の数だけ見ればよい。

観察 3.3　比が $10^{15}$ を超える。$6.082\times10^{15}$ 倍、同じグラフ、同じ「一周する」という言葉である。

観察 3.4　比そのものが $n$ で急に増える。$n=10$ で $3.629\times10^{4}$ 倍、$n=20$ で $6.082\times10^{15}$ 倍、$n$ を $2$ 倍にして、比が $11$ 桁増えた。

観察 3.5　だから小さい例では差が見えない。$n=10$ なら $0.2$ 秒、手元で試せる範囲では、二つは同じくらい簡単に見える。

4. 弦を一本足す

計算 4.1：六角形の輪に、向かい合う頂点を結ぶ弦を一本足す。

観察 4.2　弦一本でオイラー回路が消える。次数が奇数の頂点が $2$ 個、その二つを見るだけで判定できる。

観察 4.3　ハミルトン閉路は変わらない。$2$ 本のまま、弦を使う閉路は $1$、$2$、$4$、$5$ を尽くせないので、新しい閉路は生まれない。

観察 4.4　つまり同じ辺一本が、片方だけを壊している。オイラーは壊れ、ハミルトンは無傷、「一周する」という言葉が同じでも、辺の追加への反応が違う。

観察 4.5　壊れた側は、壊れたことを二頂点で示せる。奇数次数の頂点、「無い」という答に、短い証書が付く。

観察 4.6　無傷の側は、無傷であることを二頂点では示せない。全走査が要る。「ある」ほうは経路を見せれば済むが、「無い」ほうには短い証書が知られていない。

5. 分離子

分離子：頂点ごとの証書があるか。

観察 5.1　あるなら、局所を見て全体が決まる。次数が偶数か、$n$ 個の独立な検査で足りる。

観察 5.2　無いなら、全体を見なければ決まらない。$(n-1)!$ 本、どの頂点も、単独では何も言わない。

観察 5.3　二つは論文300 の基準で別根である。どちらも「一周できるか」、一方は局所の性質の連言、一方はそうでない。判定の型が違う。

観察 5.4　論文348 は同じ対比を別の分離子で切った。繋ぐのは安く、並べるのは高い。あちらの分離子は「順序を要求するか」だった。本稿は「局所の証書があるか」で切っており、同じ現象に二つの切り口がある。

観察 5.5　弦の実験が、二つの分離子を見分ける。順序はどちらの問いも要求している。それでも弦一本の反応が違うのだから、効いているのは順序ではなく証書の側である。

観察 5.6　これは論文481 でいう分離子の一本である。「この問題は難しい」という主張が問われたとき、規模が大きいのか、局所の証書が無いのかで、直す先が違う。

観察 5.7　正直に言えば、総当たりの本数は上限であって、必要な手間ではない。分枝限定法を使えば、多くの場合はずっと早く終わる。本稿が測ったのは「何も工夫しないとどうなるか」であり、ハミルトン閉路問題が本質的に難しいことの証明ではない。それは計算量理論の側の話である。

6. 点呼と結び

1. 全走査が $(n-1)!$ に一致（観察 2.2）：$n=10$ で $362880$ 本。
2. 有効な閉路は $2$ 本（観察 2.3）：往路と復路。
3. $2$ 本のために $362880$ 本（観察 2.4）：無いことの確認が高い。
4. 増え方が $8.0000$ から $9.0000$ へ（観察 2.5）：階乗である。
5. $n=20$ で比 $6.082\times10^{15}$ 倍（計算 3.1）：$n=10$ では $3.629\times10^{4}$ 倍。
6. 弦一本でオイラーが消える（観察 4.2）：奇数次数が $2$ 個。
7. ハミルトンは $2$ 本のまま（観察 4.3）：本稿の芯。
8. 壊れた側には短い証書が付く（観察 4.5）：二頂点で示せる。
9. 分離子は局所の証書があるか（観察 5.3）：論文300 の基準で別根。
10. 総当たりは上限である（観察 5.7）：難しさの証明ではない。

結び：一筆書きと巡回路は、どちらもグラフを一周する問題だと思われている。辺を尽くすか頂点を尽くすか、似た形の問いに見えるという像である。だが片方は頂点ごとに答が読める。次数が偶数かどうかであり、もう片方にはそういう読み方が知られていない。全走査を数える。輪グラフで全部の並びを走査すると、本数は $n=6$ で $120$、$8$ で $5040$、$9$ で $40320$、$10$ で $\mathbf{362880}$ となり、閉じた式 $(n-1)!$ に一致する。有効なハミルトン閉路はどの $n$ でも $\mathbf{2}$ 本で、輪グラフには往路と復路の二通りしかない。答が $2$ 本しかないのに $362880$ 本を調べており、見つけるのが難しいのではなく、無いことを確かめるのが高い。増え方自体が増え、$n$ を $8$ から $9$ にすると $\mathbf{8.0000}$ 倍、$9$ から $10$ にすると $\mathbf{9.0000}$ 倍、指数なら比が一定になるはずで、そうならない。階乗である。$n=20$ で測る。オイラー判定は次数 $\mathbf{20}$ 個を見るだけで $0.000000$ 秒、ハミルトンの全走査は $\mathbf{1.216451\times10^{17}}$ 本、比は $\mathbf{6.082\times10^{15}}$ 倍である。同じグラフ、同じ「一周する」という言葉である。比そのものが $n$ で急に増え、$n=10$ では $3.629\times10^{4}$ 倍にすぎない。$n$ を $2$ 倍にして、比が $11$ 桁増えた。だから小さい例では差が見えず、$n=10$ なら $0.2$ 秒で終わって、手元で試せる範囲では二つは同じくらい簡単に見える。弦を一本足す。六角形の輪に向かい合う頂点を結ぶ弦を足すと、次数が奇数の頂点が $\mathbf{2}$ 個できてオイラー回路が消える。その二つを見るだけで判定できる。ところがハミルトン閉路は $\mathbf{2}$ 本のまま変わらない。弦を使う閉路は $1$、$2$、$4$、$5$ を尽くせないので、新しい閉路は生まれない。つまり同じ辺一本が片方だけを壊しており、「一周する」という言葉が同じでも、辺の追加への反応が違う。壊れた側は、壊れたことを奇数次数の二頂点で示せる。「無い」という答に短い証書が付く。無傷の側は、無傷であることを二頂点では示せず、全走査が要る。「ある」ほうは経路を見せれば済むが、「無い」ほうには短い証書が知られていない。分けているものは一つ、頂点ごとの証書があるか。あるなら局所を見て全体が決まり、$n$ 個の独立な検査で足りる。無いなら全体を見なければ決まらず、$(n-1)!$ 本を走査することになる。どの頂点も、単独では何も言わない。二つは論文300 の基準で別根であり、どちらも「一周できるか」だが、一方は局所の性質の連言、一方はそうでない。判定の型が違う。論文348 は同じ対比を別の分離子で切り、繋ぐのは安く並べるのは高いとして「順序を要求するか」を置いた。本稿は「局所の証書があるか」で切っており、同じ現象に二つの切り口がある。そして弦の実験が二つの分離子を見分ける。順序はどちらの問いも要求しているのに、弦一本への反応が違うのだから、効いているのは順序ではなく証書の側である。これは論文481 でいう分離子の一本で、「この問題は難しい」という主張が問われたとき、規模が大きいのか局所の証書が無いのかで直す先が違う。正直に言えば、総当たりの本数は上限であって、必要な手間ではない。分枝限定法を使えば多くの場合はずっと早く終わる。本稿が測ったのは「何も工夫しないとどうなるか」であって、ハミルトン閉路問題が本質的に難しいことの証明ではない。それは計算量理論の側の話である。

参考文献

1. Bondy, J. A., & Murty, U. S. R. (2008). Graph Theory. Springer.
2. Euler, L. (1736). Solutio problematis ad geometriam situs pertinentis. Commentarii Academiae Scientiarum Petropolitanae.
3. Karp, R. M. (1972). Reducibility Among Combinatorial Problems. In Complexity of Computer Computations, Plenum.
4. 山岸勇輝 (2026). 『三百本目の点呼、同根か別根かは、判定できる』[論文300]. Zenodo. 10.5281/zenodo.22171914
5. 山岸勇輝 (2026). 『同じグラフで、繋ぐのは安く、並べるのは高い』[論文348]. Zenodo. 10.5281/zenodo.22683555
6. 山岸勇輝 (2026). 『「法則が破れた」は、どの仮定へも落とせる』[論文481]. Zenodo. 10.5281/zenodo.22733927
7. 山岸勇輝 (2026). 『三つの別々の答は、どれも「接する」ところで決まっている』[論文507]. Zenodo. 10.5281/zenodo.22861868

作成にあたって：本稿の着想と内容は、著者自身の考察に基づくものです。文章の構成整理や英訳、数式の確認には AI（大規模言語モデル）の助力を得ました。最終的な内容の解釈や誤りがあれば、それらはすべて著者の責に帰します。お気づきの点があれば、ご教示いただければ幸いです。

書誌

山岸勇輝（2026）「弦を一本足すと、局所で確かめられる性質だけが壊れる」［論文508］. Zenodo.
DOI: 10.5281/zenodo.22861925

@misc{yamagishi2026yoi508,
  author = {Yamagishi, Yuuki},
  title = {Adding One Chord Destroys Only the Property That Has a Local Certificate},
  year = {2026},
  howpublished = {YOI: https://www.yamagishiyuuki.com/yoi/508},
  doi = {10.5281/zenodo.22861925},
  note = {Preprint, edition 1}
}