0-rotatability of spiders with three equal arms of length three or four

Research note

This note belongs to the Three equal long arms: zero-rotatability at lengths three and four project.

Statement and terminology

For k equal to 3 or 4 and any integer m >= 1, let S_(k,m)=S(k,k,k,1^m) be the tree with center c, three long arms a_i1,...,a_ik for i=0,1,2 (in order away from c), and m additional leaves p_0,...,p_(m-1) adjacent to c. It has q=3k+m edges. A graceful labeling is a bijection from its vertices to {0,...,q} whose edge differences are {1,...,q}.

Theorems A and B. For each k in {3,4} and every integer m >= 1, S_(k,m) is 0-rotatable: given any vertex v, there is a graceful labeling with f(v)=0. The statement makes no claim for other k.

Theorem A: five base certificates for arms of length three

For k=3 and m=1, the following rows give one certificate for each vertex orbit. Each arm triple lists labels at depths 1, 2 and 3. t is the fixed insertion threshold used below. The column d is the difference of the edge to the next inserted leaf.

Every row uses vertex labels 0,...,10 exactly once. For each row, classify an edge as same-side if both endpoint labels are at most t or both exceed t, and crossing otherwise. Direct calculation gives the following disjoint difference intervals; every difference within each interval occurs once.

Thus each row is graceful. The exact checker and the independent audit in the package verify all individual edges as sorted lists, so duplicates are not hidden by set comparisons.

Threshold-insertion lemma

Let a tree T have q edges, a graceful labeling f, a vertex c where a leaf will be attached, and a fixed integer 0 <= t <= q. Set

d=t+1-f(c) if f(c)<=t, and d=f(c)-t if f(c)>t.

Suppose the same-side edges have differences 1,...,d-1 exactly once, while crossing edges have differences d,...,q exactly once. Insert a new leaf at c, shift each old label above t upward by one, and give the new leaf label t+1:

f+(v)=f(v)+1_[f(v)>t] for old vertices; f+(new leaf)=t+1.

The old labels become 0,...,t,t+2,...,q+1; the new label fills the only gap. Old same-side differences stay fixed. Every old crossing difference rises by one. The new leaf edge has difference d. Hence the new differences are exactly 1,...,d-1, d, and d+1,...,q+1, each once.

The interval hypothesis also persists with the same threshold t:

1. If f(c)<=t, the center remains low and the new leaf is high. Their edge is crossing with difference d. The same-side interval remains 1,...,d-1; the shifted old crossing interval is d+1,...,q+1, so with the new edge it is d,...,q+1. The parameter d is unchanged.
2. If f(c)>t, the center rises by one and both center and new leaf lie above t. Their edge is same-side with difference d. The next parameter is d'=d+1; the same-side interval is 1,...,d (equivalently 1,...,d'-1), and the shifted crossing interval is d'=d+1,...,q+1.

The invariant can therefore be iterated for arbitrarily many new center leaves. The vertex carrying zero is unchanged: zero never exceeds t, and the new leaf gets the positive label t+1.

Apply this lemma repeatedly to each of the five length-three base rows. These rows cover the center, all three depths on a long arm, and a short center leaf. Permuting the three long arms or the short leaves moves any prescribed vertex into the corresponding row's zero position. This proves Theorem A for every m >= 1.

Theorem B: six base certificates for arms of length four

For k=4, the same lemma applies to six different base rows at m=1, where q=13. Each arm quadruple lists vertex labels at depths 1 through 4. Every row uses all labels 0,...,13 exactly once and all edge differences 1,...,13 exactly once. The final two columns give the fixed threshold and next-leaf difference.

For these rows, the same-side differences are respectively 1,...,13, 1,...,7, 1,...,6, 1,...,9, 1,...,2, and 1,...,12. The crossing differences are the complementary consecutive intervals d,...,13 (empty in the center row). Each individual difference occurs once, as checked in k4_bases.json, k4_verify.py, and the separate audit-k4.md.

The fixed-threshold lemma therefore extends all six rows to every m >= 1, preserving zero at its original vertex. The six orbits are the center, arm depths 1 through 4, and a short center leaf. Arm and short-leaf permutations cover every prescribed vertex. This proves Theorem B.

Reproduce the certificates

The package graceful-spider-three-arms-proof.zip contains both base-data files, verify_proof.py, k4_verify.py, the search code, proof notes, literature notes, two separate audit reports, and BUNDLE-README.md. Its SHA-256 is 86b4e0f5c01a8f43a4579894e891a3ef362c675280ca70a75b9df790b064b549. After unpacking it, run python verify_proof.py and python k4_verify.py. On 8 October 2026, Python 3.12.1 checked every base row and the interval invariant through m=100 for both families. The results for all m follow from the lemma and the vertex-orbit argument above.

The two separate audit reports in the package reconstruct the base cases without importing the project checkers and report PASS for the stated constructions.

Relation to earlier work

Patterson's 2017 thesis proposed a broader conjecture about 0-rotatable spiders (Conjecture 5.4.4), with an exceptional family. Its reported finite census includes small cases from the two families here, but does not settle all m. We could not inspect the full thesis page by page; its precise conjecture should be checked against the original before an originality claim is submitted. Rofa's 2023 result concerns rooted symmetric trees and spiders with equal leg lengths. Bahls, Lake, and Wertheim proved gracefulness for related spiders, which is weaker than 0-rotatability. A related label-gap insertion method was described publicly before this work.

The targeted search found neither exact all-m theorem, but does not establish publication priority. The present proof covers only S(3,3,3,1^m) and S(4,4,4,1^m) for integers m >= 1.