Degree-Preserving Structural Perturbations and CDCL Behavior in Tseitin Formulas

Tseitin formulas provide a controlled setting in which graph structure can be related to propositional proof search. We study randomized degree-preserving double-edge swaps of a 4-regular ring on 80 vertices, holding the 160 edges and complete degree sequence fixed. In a 300-instance discovery campaign with instrumented Kissat 4.0.4, the fraction exceeding a 60-second budget rises from 3.3% at 16 requested swaps to 36.7% at 20, 76.7% at 24, 96.7% at 32, and 100% at 48 and 80. A separate 200-instance confirmation replicated the prespecified within-swap associations: runs censored under the campaign presentation had higher global efficiency and lower modularity at both 20 and 24 swaps. Exploratory censored accelerated-failure-time (AFT) analyses yielded positive predictive gains for global efficiency in several evaluations beyond the stated approximate baselines. After a fixed-graph pilot, we prespecified a robustness campaign with 60 outcome-blind selected graphs and five joint variable-renumbering and clause-order presentations each. In this sample, 24 of 60 graphs exhibited both resolved and censored outcomes across the five presentations. Higher efficiency retained a negative adjusted association with resolution probability (coefficient −1.525, graph-bootstrap 95% interval [−2.446, −0.688]), including after a treewidth-squared sensitivity, but its held-out log-score gain was +0.02265 with interval [−0.01130, +0.05959]. Under the frozen three-part rule, robustness was not established: the adjusted association was recovered, whereas additional predictive value was inconclusive. This does not imply absence of an effect.