Gap Extensions of Graceful Labelings: a Characterization, a Transformation Law, and Self-Replication

A recently described inductive approach to the Graceful Tree Conjecture (MathWorld, "Graceful Tree Theorem," accessed 15 August 2026) grows a gracefully labeled tree by inserting a gap into its label set and attaching a new leaf at a designated root. The approach appears there with experimental evidence — verification for all rooted trees on at most 20 vertices — and without a structure theory. We supply that theory. We characterize exactly when a gap extension preserves gracefulness: the label-threshold cut must coincide with a top tail of the difference spectrum. The classical alpha-labelings of Rosa and the pendant-at-extreme constructions are recovered as the two boundary strata of this characterization. We then prove a complete transformation law: the set of cut-tail coincidences (the match set) of the extended labeling is the image of the original match set under exactly six affine moves gated by root-position inequalities. Two consequences follow. First, a self-replication theorem: a labeling extended through a gap point always admits a further extension at the same root; consequently any vertex admitting one extension absorbs unboundedly many leaves, and the only obstruction to the inductive program is root switching. Second, a diagonal transport lemma determining exactly which extension opportunities at other vertices survive an extension. All results carry short elementary proofs and have been verified exhaustively by machine over all 137,250 graceful gap extensions arising from all rooted trees on at most 8 vertices, with code and data released.