Abstract
One set of points admits two questions: the minimum spanning tree and the travelling salesman. This paper asks why only one of them is hard——the answer is whether an order of visiting is demanded. No new mathematical theorem and no new law is claimed.
First, at $n=20$ there are $6.0823\times10^{16}$ tours, taking $\mathbf{19.2735}$ years at a hundred million a second (Section 2).
Second, the spanning tree on the same $n=20$ takes about $n^2=400$ operations (Section 2).
Third, this is the core of the paper. What makes the difference is not the number of points but whether an order is demanded (Section 3).
Fourth, it was measured on this corpus’s own citation graph. All $337$ papers are joined by $\mathbf{336}$ edges (Section 4).
Fifth, the skeleton is $\mathbf{14.0234}$ per cent of the $2396$ edges, and the remaining $85.9766$ per cent is redundant as a tree (Section 4).
Sixth, the separator is whether order is needed or connection alone suffices (Section 5).
Scope (what is not claimed)
No new mathematical theorem and no new law is claimed——the count of tours $(n-1)!/2$, the algorithms of Prim and Kruskal, and the classification of complexity are all standard. We do not build complexity theory——proofs of NP-hardness and the relation of P to NP are not entered. They are mentioned and no more. We do not treat approximation algorithms——approximation ratios such as Christofides’s are not entered. Only the size of exhaustive search is looked at. We do not treat weighted spanning trees——this corpus’s graph carries no weights, so a minimum spanning tree and any spanning tree have the same number of edges. Optimisation under weights is not entered. We do not evaluate the content of the corpus——no judgement about which papers matter; only the presence of edges is counted. We do not settle the structure of a collected edition——no proposal for dividing volumes; only numbers. Relation to earlier papers: Paper 324 showed that no search is universal because of how the problems are counted——there too the difficulty came from the counting and not from the problem. Here one set of points admits two countings, and only one explodes. Paper 316 showed the same integer returning from three different counts——there the counts differed and the answer agreed. Here the object is one and the strength of the demand differs. Paper 300 showed whether two things share a root is decidable——the two questions have distinct roots by that test. Paper 347 showed “cannot be constructed” to be a property of the tools——there the tools raise the wall; here the demand does. Both place the source of difficulty outside the object. What is added is tabulating tour counts against spanning-tree effort, actually constructing a spanning tree on this corpus’s citation graph and measuring $336$ edges, confirming that halving the edges disconnects it, which bounds what “redundant” means, and putting the separator on whether order is demanded.
1. Notation and the Question
Setting: Given $n$ points and edges joining them, ask two questions.
| Question | What is sought | Demand |
|---|---|---|
| Minimum spanning tree | a set of edges joining all | connectedness |
| Travelling salesman | a tour visiting each once | connectedness and order |
Observation 1.1 The input is identical. The same points, the same edges, the same weights——what differs is only what is demanded of the answer.
Observation 1.2 And only one is practically solvable. A spanning tree is found for $n$ in the tens of thousands, while exhaustive search for a tour collapses in the tens——two questions on one input, divided by feasibility.
Observation 1.3 The way of measuring is fixed first. Tours are counted as $(n-1)!/2$, identifying rotations of the start and reversals, and a machine examines a hundred million a second——this measures the size of exhaustive search, not the speed of the best known algorithm.
Question: On one input, why is only one of them hard?
2. At $n=20$: $400$ Operations Against $19.2735$ Years
Calculation 2.1: Tour counts and the time at a hundred million a second (computed in this paper).
| $n$ | Tours $(n-1)!/2$ | At $10^8$ per second |
|---|---|---|
| $10$ | $1.8144\times10^{5}$ | $0.0018$ s |
| $15$ | $4.3589\times10^{10}$ | $435.8915$ s |
| $\mathbf{20}$ | $\mathbf{6.0823\times10^{16}}$ | $\mathbf{19.2735}$ years |
| $25$ | $3.1022\times10^{23}$ | $9.8304\times10^{7}$ years |
| $30$ | $4.4209\times10^{30}$ | $1.4009\times10^{15}$ years |
Observation 2.2 Two checks. (a) At $n=5$ there are $12$ tours, the textbook value. (b) At $n=10$ there are $181440$, agreeing with $9!/2$——the counting is confirmed on two known cases before the table is read.
Observation 2.3 From $n=15$ to $n=20$, five more points turn $435.8915$ seconds into $19.2735$ years. $1.4$ times the points, $\mathbf{1395360}$ times the time——that is how a factorial grows.
Observation 2.4 At $n=30$ it is $1.4009\times10^{15}$ years, a hundred thousand times the age of the universe. Thirty points——at a scale one can draw on paper, exhaustive search outlasts the universe.
Calculation 2.5: Spanning-tree effort at the same $n$ (Prim’s algorithm, about $n^2$; computed in this paper).
| $n$ | Tours | Spanning-tree effort $n^2$ | Ratio |
|---|---|---|---|
| $10$ | $1.8144\times10^{5}$ | $100$ | $1.8144\times10^{3}$ |
| $20$ | $6.0823\times10^{16}$ | $400$ | $\mathbf{1.5206\times10^{14}}$ |
| $30$ | $4.4209\times10^{30}$ | $900$ | $\mathbf{4.9121\times10^{27}}$ |
Observation 2.6 Treble $n$ and the spanning-tree effort merely multiplies by nine. From $100$ to $900$——for the same trebling, the tour count multiplies by $2.4\times10^{25}$.
3. The Core: What Makes the Difference Is Whether an Order Is Demanded
Observation 3.1 This is the core of the paper. A spanning tree settles only which edges are used——the answer is a set of edges, and edges carry no order.
Observation 3.2 The travelling salesman settles in which order the points are visited. The same set of edges traversed in a different order is a different answer——the answer is a sequence, not a set, and so the counting becomes factorial.
Observation 3.3 And the demand for order breaks the greedy method. For a spanning tree, repeatedly taking the lightest available edge gives the optimum (Kruskal)——for a tour, always going to the nearest point does not, because it costs later.
Observation 3.4 This is where the complexity divides. The spanning tree is polynomial and the travelling salesman is NP-hard——this paper does not enter the proof, but that the division sits on “order” is visible in the counting.
Observation 3.5 Apply the criterion of Paper 300.
| Criterion | Result |
|---|---|
| Is there a correspondence preserving an identity | No. No unique map from a set to a sequence |
| Does the same quantity appear | No. $n-1$ edges against $(n-1)!/2$ sequences |
| Is the relation kept as variables move | No. As $n$ grows one is polynomial, one factorial |
Observation 3.6 All three point to distinct roots. Sharing an input——they differ only in the strength of the demand, and that makes them different problems.
Observation 3.7 It pairs with Paper 347. Paper 347 wrote that “cannot be constructed” is a property of the tools——there the tools raise the wall; here the demand does. Both place the source of difficulty outside the object.
4. Measured on This Corpus’s Own Graph
Setting: Rather than stop at the abstract, measure a graph that exists. Take this corpus’s internal citation graph——nodes are papers and edges are citations.
Calculation 4.1: Build the citation graph and construct a spanning tree (computed in this paper).
| Quantity | Value |
|---|---|
| Nodes (papers) | $\mathbf{337}$ |
| Directed edges (citations) | $2433$ |
| Undirected edges | $\mathbf{2396}$ |
| Connected components | $\mathbf{1}$ |
| Edges in the spanning tree | $\mathbf{336}$ |
| Skeleton as a fraction | $\mathbf{14.0234}$ per cent |
| Redundant edges | $2060$ ($85.9766$ per cent) |
Observation 4.2 Three checks. (a) The $336$ edges match “nodes minus components”, $337-1$. (b) There is one component, so no paper stands isolated. (c) Halving the edges breaks the graph into $79$ components——the third is the one that works. Redundant does not mean any edge may be discarded.
Observation 4.3 $336$ edges join all $337$ papers. That is $14.0234$ per cent of the $2396$——to make the corpus one connected thing takes a seventh of its citations.
Observation 4.4 Yet the tours through the same $337$ points number $10^{704.3}$. $336$ edges to connect, $10^{704.3}$ tours to order——two questions about one corpus, that far apart.
Observation 4.5 This touches a real question, the structure of a collected edition. “Which paper to place beside which” is near the spanning-tree question, and “in what order to arrange them all” is near the tour question——the first can be computed and the second cannot. This paper proposes no division into volumes, but the two questions have measurably different prices.
Observation 4.6 To be stated honestly——this corpus’s graph carries no weights. So a “minimum” spanning tree and any spanning tree have the same number of edges——$336$ follows from connectedness and is not the result of an optimisation. Add weights and which $336$ becomes the question.
Observation 4.7 And the redundant $85.9766$ per cent is not waste. Halving the edges broke the graph into $79$ pieces, which says so——being redundant as a tree and being dispensable are different things. The redundancy is the freedom in which $336$ to choose.
5. The Separator: Is Order Needed, or Does Connection Suffice?
Observation 5.1 The separator——whether the answer may be a set of edges or must be a sequence of points.
| Form of the answer | Number of candidates | Greedy method | |
|---|---|---|---|
| Spanning tree | a set | searchable in polynomial time | reaches the optimum |
| Tour | a sequence | $(n-1)!/2$ | does not |
Observation 5.2 The separator is not on the side of the graph. The same points, the same edges, the same weights——what makes the difference is only what was demanded of the answer.
Observation 5.3 The separator can be moved. Drop the condition of visiting each point once and allow repeats, and a walk tracing the spanning tree twice becomes available——not shortest, but a feasible answer in polynomial time. Loosen one demand and the factorial disappears.
Observation 5.4 And that walk is no longer than twice the spanning tree. Since an optimal tour is at least the length of the spanning tree, this method stays within twice the optimum——unable to answer the hard question, one gets a guarantee from the answer to the easy one.
Observation 5.5 Where this stands relative to Paper 324. Paper 324 wrote that no search is universal because of how the problems are counted——there too the difficulty came from the counting and not from the problem. Here one object admits two countings and only one explodes.
Observation 5.6 One last thing——$336$ and $10^{704.3}$ are two numbers about one corpus. One comes out in seconds and the other cannot be enumerated in principle——the difficulty is not in the corpus but in what was demanded of it.
6. The Census and the Close
- $19.2735$ years at $n=20$ (Calculation 2.1): at a hundred million a second.
- $12$ tours at $n=5$, $181440$ at $n=10$ (Observation 2.2): textbook values.
- Five more points, $1395360$ times the time (Observation 2.3): how a factorial grows.
- $1.4009\times10^{15}$ years at $n=30$ (Calculation 2.1): a hundred thousand times the universe.
- Treble $n$, spanning tree by nine (Observation 2.6): tours by $2.4\times10^{25}$.
- A set against a sequence (Observation 3.2): a sequence makes it factorial.
- $337$ papers joined by $336$ edges (Calculation 4.1): $14.0234$ per cent of $2396$.
- $10^{704.3}$ tours through the same points (Observation 4.4): two questions, one corpus.
- Halving the edges gives $79$ components (Observation 4.2): redundant is not dispensable.
- Dropping “once each” removes the factorial (Observation 5.3): one demand loosened.
Closing: One set of points and edges admits two questions, the minimum spanning tree and the travelling salesman, and the input is identical: only what is demanded of the answer differs——and only one of them is practically solvable. At $n=20$ there are $6.0823\times10^{16}$ tours, taking $\mathbf{19.2735}$ years at a hundred million a second——from $435.8915$ seconds at $n=15$, five more points multiply the time by $\mathbf{1395360}$. At $n=30$ it is $1.4009\times10^{15}$ years, a hundred thousand times the age of the universe — at a scale one can draw on paper, exhaustive search outlasts the universe. The spanning tree on the same $n=30$ takes about $n^2=900$. What makes the difference is not the number of points——a spanning tree settles only which edges are used, and its answer is a set carrying no order. The travelling salesman settles in which order the points are visited, and its answer is a sequence, which makes the counting factorial. And the demand for order breaks the greedy method: taking the lightest edge repeatedly gives the optimal tree, while going always to the nearest point does not give the optimal tour. Rather than stop at the abstract, it was measured on a graph that exists——this corpus’s internal citation graph has $\mathbf{337}$ nodes and $\mathbf{2396}$ undirected edges in one component. Its spanning tree has $\mathbf{336}$ edges, $\mathbf{14.0234}$ per cent of the whole. To make the corpus one connected thing takes a seventh of its citations. Yet the tours through the same $337$ points number $\mathbf{10^{704.3}}$. This touches a real question——“which paper to place beside which” is near the spanning-tree question and “in what order to arrange them all” is near the tour question; the first can be computed and the second cannot. One thing separates them——whether the answer may be a set of edges or must be a sequence of points. The separator is not on the side of the graph——the same points, edges and weights, and only the demand differs. And it can be moved——drop “each point once” and a walk tracing the spanning tree twice becomes available in polynomial time; since an optimal tour is at least the length of the tree, that walk stays within twice the optimum. Unable to answer the hard question, one gets a guarantee from the answer to the easy one. To be said honestly——this corpus’s graph carries no weights, so a “minimum” spanning tree and any spanning tree have the same edge count: $336$ follows from connectedness, not from an optimisation. And the redundant $85.9766$ per cent is not waste — halving the edges broke the graph into $79$ pieces. Being redundant as a tree and being dispensable are different things. One last thing——$336$ and $10^{704.3}$ are two numbers about one corpus. One comes out in seconds and the other cannot be enumerated in principle. The difficulty is not in the corpus but in what was demanded of it.
References
- Boruvka, O. (1926). O jistém problému minimálním. Práce Moravské Přírodovědecké Společnosti, 3.
- Kruskal, J. B. (1956). On the Shortest Spanning Subtree of a Graph and the Traveling Salesman Problem. Proceedings of the American Mathematical Society, 7(1).
- Prim, R. C. (1957). Shortest Connection Networks and Some Generalizations. Bell System Technical Journal, 36(6).
- Karp, R. M. (1972). Reducibility Among Combinatorial Problems. In: Complexity of Computer Computations. New York: Plenum.
- Christofides, N. (1976). Worst-Case Analysis of a New Heuristic for the Travelling Salesman Problem. Carnegie Mellon University, Management Sciences Research Report 388.
- 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). The Same Integer Comes Back from Three Different Counts [Paper 316]. Zenodo. 10.5281/zenodo.22208229
- Yamagishi, Y. (2026). That No Search Is Universal Follows from How the Problems Are Counted [Paper 324]. Zenodo. 10.5281/zenodo.22209395
- Yamagishi, Y. (2026). “Cannot Be Constructed” Is a Property of the Tools, Not of the Figure [Paper 347]. Zenodo. 10.5281/zenodo.22682365
Reference
Yamagishi, Y. (2026). On the Same Graph, Connecting Is Cheap and Ordering Is Not [Paper 348]. YOI: https://www.yamagishiyuuki.com/yoi/348
DOI: 10.5281/zenodo.22683555
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 348. This paper is a preprint and has not been peer reviewed.