Adding One Chord Destroys Only the Property That Has a Local Certificate ── Add one chord to a hexagon and 2 vertices acquire odd degree, so the Euler circuit vanishes ── yet the number of Hamiltonian cycles stays at 2 ── [Paper 508]

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. Scope of this paper (scope note): No new theorem or law is claimed──Euler’s theorem and the NP-completeness of the Hamiltonian cycle problem are both standard. No complexity theory is built──proofs of NP-completeness and the relation between P and NP are not entered; only the size of an exhaustive scan is counted. No good algorithm is used──no branch and bound, no dynamic programming. The exhaustive count is an upper bound, not the work actually required. Only small graphs were scanned──exhaustive scanning reaches n=10; the value at n=20 was computed from (n-1)!. Connectivity is not part of the check──the connectivity half of Euler’s condition is trivial on a cycle graph, so only degrees were examined. Relation to earlier papers: Paper 348 showed that on the same graph connecting is cheap and ordering is not, placing its separator at whether an order is demanded──this paper’s separator is a different one: whether a certificate exists at each vertex. Paper 300 showed that a shared root can be decided──the two circuits are distinct roots. Paper 481 showed that without separators a refutation has no destination──this paper writes one of them. Paper 507 set three answers side by side, all decided where something is tangent──likewise a case of similar-looking questions of different type. What is added is confirming the exhaustive count against (n-1)!, counting the valid cycles as 2, showing the growth moving from 8.0000 to 9.0000, setting the cost ratios at n=10 and n=20 side by side, and measuring that one chord destroys only one of the two. First, the exhaustive count on a cycle graph matches (n-1)!, reaching 362880 at n=10 (Section 2). Second, the number of valid Hamiltonian cycles is exactly 2 at every n, one each way round (Section 2). Third, raising n by one multiplies the scan by 8.0000 and then by 9.0000: the growth itself grows (Section 2). Fourth, at n=20 it is 20 degrees against 1.216451x10^17, a ratio of 6.082x10^15──where at n=10 it is only 3.629x10^4 (Section 3). Fifth, this is the core of the paper. Adding one chord removes the Euler circuit while the Hamiltonian count stays at 2 (Section 4). Sixth, the separator is whether there is a certificate at each vertex (Section 5). Tracing every edge and visiting every vertex are taken to be two forms of one problem──exhaust the edges, or exhaust the vertices: questions of similar shape. But one can be read off vertex by vertex, by whether the degree is even, and for the other no such reading is known. Counting the exhaustive scan──scanning all orderings on a cycle graph gives 120, 5040, 40320 and 362880 at n=6, 8, 9 and 10, matching (n-1)!. The valid Hamiltonian cycles number 2 at every n, one each way round. Two answers, and 362880 orderings examined: finding one is not the difficulty, confirming that none remains is. And the growth itself grows──8.0000 from 8 to 9, 9.0000 from 9 to 10──where an exponential would hold the ratio fixed. It is factorial. Measuring at n=20──the Euler check reads 20 degrees in 0.000000 seconds while the exhaustive scan is 1.216451x10^17 orderings, a ratio of 6.082x10^15. The same graph, the same phrase “go round once”. The ratio itself grows sharply with n: 3.629x10^4 at n=10 against 6.082x10^15 at n=20, so doubling n added eleven orders. So the difference is invisible on small examples──at n=10 it takes 0.2 seconds, and within what can be tried by hand the two look equally easy. Adding one chord──adding a chord joining opposite vertices of a hexagon gives 2 vertices of odd degree, and the Euler circuit vanishes; reading those two settles it. Yet the Hamiltonian cycles remain 2, since a cycle using the chord cannot exhaust 1, 2, 4 and 5. So one and the same edge destroys only one of them: the phrase “go round once” is shared, but the response to an added edge is not. The broken one can be shown broken at two vertices, so the answer “no” comes with a short certificate. The intact one cannot be shown intact at two vertices; “yes” is settled by exhibiting a path, but for “no” no short certificate is known. One thing separates them──is there a certificate at each vertex. If there is, the local settles the global, and n independent checks suffice. If there is not, only the global settles it, and no single vertex says anything on its own. The two are distinct roots by the criterion of Paper 300: both ask whether the graph can be traversed once round, but one is a conjunction of local properties and the other is not. Paper 348 cut the same contrast with a different separator, whether an order is demanded, while this paper cuts on whether a local certificate exists──one phenomenon admitting two cuts. And the chord experiment tells the two apart: both questions demand an order, yet they respond differently to one chord, so what is at work is the certificate and not the order. This is one of the separators of Paper 481: when “this problem is hard” is questioned, whether the instance is large or no local certificate exists sends the repair elsewhere. To be honest──the exhaustive count is an upper bound, not the work required. Branch and bound finishes far sooner in most cases, and what is measured here is what happens with no cleverness at all, not a proof that the Hamiltonian cycle problem is intrinsically hard. That belongs to complexity theory. On the making of this work: The ideas and content of this work stem from the author's own considerations. Assistance from an AI (a large language model) was used for structuring, English translation, and checking the algebra. Any remaining errors or misinterpretations are solely the author's. Feedback and corrections are sincerely appreciated. Keywords: Euler path, Hamiltonian cycle, NP-completeness, graph theory, local certificate. ----- 一筆書きと巡回路は、どちらもグラフを一周する問題だと思われている。本稿が示すのは、同じ辺を一本足すと、片方だけが壊れることである──片方には頂点ごとの証書があり、片方には無い。新しい定理も法則も主張しない。 本稿の射程(射程注記):新しい定理も法則も主張しない──オイラーの定理も、ハミルトン閉路問題が 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 で並べたこと、弦一本で片方だけが壊れることを実測したことである。 第一に、輪グラフの全走査の本数は (n-1)! に一致し、n=10 で 362880 本である(第2節)。 第二に、有効なハミルトン閉路はどの n でもちょうど 2 本(往路と復路)である(第2節)。 第三に、n を 1 増やすと走査が 8.0000 倍、次は 9.0000 倍と、増え方自体が増える(第2節)。 第四に、n=20 では次数 20 個 対 1.216451x10^17 本、比は 6.082x10^15 倍である──n=10 ではまだ 3.629x10^4 倍にすぎない(第3節)。 第五に、これが本稿の芯である。弦を一本足すとオイラー回路は消えるが、ハミルトン閉路は 2 本のままである(第4節)。 第六に、分離子は「頂点ごとの証書があるか」である(第5節)。 一筆書きと巡回路は、どちらもグラフを一周する問題だと思われている──辺を尽くすか頂点を尽くすか、似た形の問いに見えるという像である。だが片方は頂点ごとに答が読める。次数が偶数かどうかであり、もう片方にはそういう読み方が知られていない。全走査を数える──輪グラフで全部の並びを走査すると、本数は n=6 で 120、8 で 5040、9 で 40320、10 で 362880 となり、閉じた式 (n-1)! に一致する。有効なハミルトン閉路はどの n でも 2 本で、輪グラフには往路と復路の二通りしかない。答が 2 本しかないのに 362880 本を調べており、見つけるのが難しいのではなく、無いことを確かめるのが高い。増え方自体が増え、n を 8 から 9 にすると 8.0000 倍、9 から 10 にすると 9.0000 倍──指数なら比が一定になるはずで、そうならない。階乗である。 n=20 で測る──オイラー判定は次数 20 個を見るだけで 0.000000 秒、ハミルトンの全走査は 1.216451x10^17 本、比は 6.082x10^15 倍である。同じグラフ、同じ「一周する」という言葉である。比そのものが n で急に増え、n=10 では 3.629x10^4 倍にすぎない。 n を 2 倍にして、比が 11 桁増えた。だから小さい例では差が見えず、n=10 なら 0.2 秒で終わって、手元で試せる範囲では二つは同じくらい簡単に見える。弦を一本足す──六角形の輪に向かい合う頂点を結ぶ弦を足すと、次数が奇数の頂点が 2 個できてオイラー回路が消える。その二つを見るだけで判定できる。ところがハミルトン閉路は 2 本のまま変わらない。弦を使う閉路は 1、2、4、5 を尽くせないので、新しい閉路は生まれない。つまり同じ辺一本が片方だけを壊しており、「一周する」という言葉が同じでも、辺の追加への反応が違う。壊れた側は、壊れたことを奇数次数の二頂点で示せる。「無い」という答に短い証書が付く。無傷の側は、無傷であることを二頂点では示せず、全走査が要る。「ある」ほうは経路を見せれば済むが、「無い」ほうには短い証書が知られていない。分けているものは一つ──頂点ごとの証書があるか。あるなら局所を見て全体が決まり、n 個の独立な検査で足りる。無いなら全体を見なければ決まらず、(n-1)! 本を走査することになる。どの頂点も、単独では何も言わない。二つは論文300 の基準で別根であり、どちらも「一周できるか」だが、一方は局所の性質の連言、一方はそうでない。判定の型が違う。論文348 は同じ対比を別の分離子で切り、繋ぐのは安く並べるのは高いとして「順序を要求するか」を置いた。本稿は「局所の証書があるか」で切っており、同じ現象に二つの切り口がある。そして弦の実験が二つの分離子を見分ける。順序はどちらの問いも要求しているのに、弦一本への反応が違うのだから、効いているのは順序ではなく証書の側である。これは論文481 でいう分離子の一本で、「この問題は難しい」という主張が問われたとき、規模が大きいのか局所の証書が無いのかで直す先が違う。正直に言えば──総当たりの本数は上限であって、必要な手間ではない。分枝限定法を使えば多くの場合はずっと早く終わる。本稿が測ったのは「何も工夫しないとどうなるか」であって、ハミルトン閉路問題が本質的に難しいことの証明ではない。それは計算量理論の側の話である。 作成にあたって:本稿の着想と内容は、著者自身の考察に基づくものです。文章の構成整理や英訳、数式の確認には AI(大規模言語モデル)の助力を得ました。最終的な内容の解釈や誤りがあれば、それらはすべて著者の責に帰します。お気づきの点があれば、ご教示いただければ幸いです。 キーワード:オイラー路、ハミルトン閉路、NP 完全、グラフ理論、局所的な証明書。