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.
Scope (what is not claimed)
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.
1. Notation and the Question
Setting: Take a cycle graph on $n$ vertices and ask two questions. Whether a circuit traverses every edge exactly once (an Euler circuit), and whether one visits every vertex exactly once (a Hamiltonian cycle). The first is settled by checking whether every degree is even. The second is approached by scanning orderings of the vertices. Below, the number scanned and the number valid are counted separately.
Observation 1.1 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, runs the picture.
Observation 1.2 But one of them can be read off vertex by vertex. Whether the degree is even—for the other, no such reading is known.
Question: Where can that difference be measured.
2. Counting the Exhaustive Scan
Computation 2.1: Count the work of both decisions on a cycle graph.
| $n$ | Euler check | Orderings scanned | Valid cycles |
|---|---|---|---|
| $6$ | $6$ degrees | $120$ | $\mathbf{2}$ |
| $8$ | $8$ degrees | $5040$ | $\mathbf{2}$ |
| $9$ | $9$ degrees | $40320$ | $\mathbf{2}$ |
| $10$ | $10$ degrees | $\mathbf{362880}$ | $\mathbf{2}$ |
Observation 2.2 The scan matches $(n-1)!$. $362880$ against $362880$—agreement with the closed form, confirming that the scan really covers everything.
Observation 2.3 The valid cycles number $2$ at every $n$. One each way round—a cycle graph admits only two.
Observation 2.4 Two answers, and $362880$ orderings examined. Fewer than one in $180{,}000$—finding one is not the difficulty; confirming that none remains is.
Observation 2.5 The growth itself grows. From $8$ to $9$ multiplies by $8.0000$, from $9$ to $10$ by $9.0000$—an exponential would hold the ratio fixed; this does not. It is factorial.
3. Measuring at $n=20$
Computation 3.1: Set the two costs side by side at $n=20$.
| Decision | Cost |
|---|---|
| Euler circuit | reading $\mathbf{20}$ degrees |
| Hamiltonian cycle (exhaustive) | $\mathbf{1.216451\times10^{17}}$ orderings |
| Ratio | $\mathbf{6.082\times10^{15}}$ |
Observation 3.2 The Euler check finishes instantly even at $n=20$. $0.000000$ seconds—it reads as many numbers as there are vertices.
Observation 3.3 The ratio exceeds $10^{15}$. $6.082\times10^{15}$—the same graph, the same phrase “go round once”.
Observation 3.4 The ratio itself grows sharply with $n$. $3.629\times10^{4}$ at $n=10$, $6.082\times10^{15}$ at $n=20$—doubling $n$ added eleven orders to the ratio.
Observation 3.5 So the difference is invisible on small examples. $0.2$ seconds at $n=10$—within what can be tried by hand, the two look equally easy.
4. Adding One Chord
Computation 4.1: Add a chord joining opposite vertices of a hexagonal cycle.
| Quantity | Before | After |
|---|---|---|
| Vertices of odd degree | $0$ | $\mathbf{2}$ |
| Euler circuit | exists | does not |
| Hamiltonian cycles | $2$ | $\mathbf{2}$ |
Observation 4.2 One chord removes the Euler circuit. Two vertices of odd degree—and reading those two settles it.
Observation 4.3 The Hamiltonian cycles are unchanged. Still $2$—a cycle using the chord cannot exhaust $1$, $2$, $4$ and $5$, so no new cycle appears.
Observation 4.4 So one and the same edge destroys only one of them. Euler broken, Hamiltonian untouched—the phrase “go round once” is shared, but the response to an added edge is not.
Observation 4.5 The broken one can be shown broken at two vertices. The odd degrees—the answer “no” comes with a short certificate.
Observation 4.6 The intact one cannot be shown intact at two vertices. The exhaustive scan is required—“yes” is settled by exhibiting a path, but for “no” no short certificate is known.
5. The Separator
The separator: is there a certificate at each vertex.
Observation 5.1 If there is, the local settles the global. Whether the degree is even—$n$ independent checks suffice.
Observation 5.2 If there is not, only the global settles it. $(n-1)!$ orderings—no single vertex says anything on its own.
Observation 5.3 The two are distinct roots by the criterion of Paper 300. Both ask “can it be traversed once round”—but one is a conjunction of local properties and the other is not: they differ in the type of decision.
Observation 5.4 Paper 348 cut the same contrast with a different separator. Connecting is cheap and ordering is not—its separator was whether an order is demanded; this paper cuts on whether a local certificate exists, so one phenomenon admits two cuts.
Observation 5.5 The chord experiment tells the two separators apart. Both questions demand an order—yet they respond differently to one chord, so what is at work is not the order but the certificate.
Observation 5.6 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.
Observation 5.7 To be honest—the exhaustive count is an upper bound, not the work required. Branch and bound finishes far sooner in most cases—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.
6. Roll Call and Closing
- The scan matches $(n-1)!$ (Observation 2.2): $362880$ at $n=10$.
- Two valid cycles (Observation 2.3): one each way round.
- $362880$ orderings for $2$ answers (Observation 2.4): confirming “none” is costly.
- Growth from $8.0000$ to $9.0000$ (Observation 2.5): factorial, not exponential.
- Ratio $6.082\times10^{15}$ at $n=20$ (Computation 3.1): $3.629\times10^{4}$ at $n=10$.
- One chord removes the Euler circuit (Observation 4.2): two odd degrees.
- Hamiltonian count stays at $2$ (Observation 4.3): the core.
- The broken one carries a short certificate (Observation 4.5): shown at two vertices.
- The separator is the local certificate (Observation 5.3): distinct roots by Paper 300.
- An upper bound, not a proof (Observation 5.7): no claim of intrinsic hardness.
Closing: 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 $\mathbf{362880}$ at $n=6$, $8$, $9$ and $10$, matching $(n-1)!$. The valid Hamiltonian cycles number $\mathbf{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—$\mathbf{8.0000}$ from $8$ to $9$, $\mathbf{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 $\mathbf{20}$ degrees in $0.000000$ seconds while the exhaustive scan is $\mathbf{1.216451\times10^{17}}$ orderings, a ratio of $\mathbf{6.082\times10^{15}}$. The same graph, the same phrase “go round once”. The ratio itself grows sharply with $n$: $3.629\times10^{4}$ at $n=10$ against $6.082\times10^{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 $\mathbf{2}$ vertices of odd degree, and the Euler circuit vanishes; reading those two settles it. Yet the Hamiltonian cycles remain $\mathbf{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.
References
- Bondy, J. A., & Murty, U. S. R. (2008). Graph Theory. Springer.
- Euler, L. (1736). Solutio problematis ad geometriam situs pertinentis. Commentarii Academiae Scientiarum Petropolitanae.
- Karp, R. M. (1972). Reducibility Among Combinatorial Problems. In Complexity of Computer Computations, Plenum.
- Yamagishi, Y. (2026). The Three Hundredth Census: Whether Two Things Share a Root Is Decidable [Paper 300]. Zenodo. 10.5281/zenodo.22171914
- Yamagishi, Y. (2026). On the Same Graph, Connecting Is Cheap and Ordering Is Not [Paper 348]. Zenodo. 10.5281/zenodo.22683555
- Yamagishi, Y. (2026). A Broken Law Can Be Blamed on Any of the Assumptions [Paper 481]. Zenodo. 10.5281/zenodo.22733927
- Yamagishi, Y. (2026). Three Separate Answers Are All Decided Where Something Is Tangent [Paper 507]. Zenodo. 10.5281/zenodo.22861868
Reference
Yamagishi, Y. (2026). Adding One Chord Destroys Only the Property That Has a Local Certificate [Paper 508]. YOI: https://www.yamagishiyuuki.com/yoi/508
DOI: 10.5281/zenodo.22861925
ORCID: 0009-0006-8587-3450
PDF (English) · PDF (Japanese) · Date proof of the English PDF (OpenTimestamps .ots) · SHA256SUMS
The record page for this paper (in Japanese, with the PDFs in each language and the date proof): YOI 508. This paper is a preprint and has not been peer reviewed.