Yamagishi Complexity Torus Lab | 山岸勇輝ラボ

論文508 の記録のページです。住所（YOI）は https://www.yamagishiyuuki.com/yoi/508 で、論文の本文は下の PDF にあります。ファイルは自分で用意した置き場所（https://yamagishi.sakuraweb.com）に置き、日付の証拠（.ots）を添えています。Zenodo でも公開しています（DOI：10.5281/zenodo.22861925）。

本文はサイトの記事でも読めます（2026年10月17日 20:35 に公開します）。

@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}
}

日付の証拠（OpenTimestamps）

2026年10月1日に、2 本の PDF の指紋（SHA-256）をまとめて OpenTimestamps に送り、ビットコインのブロック 969428・969440・969461 に記録されました（2026年10月01日 17:42（日本時間））。この .ots があれば、PDF がその時点で存在したことを、このサイトや運営者を信用しなくても、誰でも確かめられます。

書誌

要旨

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

第一に、輪グラフの全走査の本数は $(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 完全、グラフ理論、局所的な証明書

Abstract

Tracing every edge and visiting every vertex are taken to be two forms of one problem.This paper shows that adding one and the same edge destroys only one of them、one has a certificate at each vertex and the other has none.No new theorem or law is claimed.

First, the exhaustive count on a cycle graph matches $(n-1)!$, reaching $\mathbf{362880}$ at $n=10$ (Section 2).

Second, the number of valid Hamiltonian cycles is exactly $\mathbf{2}$ at every $n$, one each way round (Section 2).

Third, raising $n$ by one multiplies the scan by $\mathbf{8.0000}$ and then by $\mathbf{9.0000}$: the growth itself grows (Section 2).

Fourth, at $n=20$ it is $\mathbf{20}$ degrees against $\mathbf{1.216451\times10^{17}}$, a ratio of $\mathbf{6.082\times10^{15}}$、where at $n=10$ it is only $3.629\times10^{4}$ (Section 3).

Fifth, this is the core of the paper.Adding one chord removes the Euler circuit while the Hamiltonian count stays at $\mathbf{2}$ (Section 4).

Sixth, the separator is whether there is a certificate at each vertex (Section 5).

Keywords: Euler path, Hamiltonian cycle, NP-completeness, graph theory, local certificate

版の記録

ここの PDF（倉庫の v1）は第1版（2026年9月）の原稿から作りました。ファイルは版ごとに分けて置いています（/yoi/508/v1/ の下）。中身を直すときは、このファイルを書き換えず、新しい版を足します（住所 https://www.yamagishiyuuki.com/yoi/508 はいつも最新の版を指します）。Zenodo の記録とは、Zenodo に上げる前の改訂のぶんだけ違うことがあります。

YOI の一覧へ