[1] OA:a5341dd6math.CO
Mean Subtree Order in Graphs with One Cycle
In every finite connected graph with exactly one cycle, a uniformly chosen subtree has strictly more vertices on average than a uniformly chosen connected vertex set. The connected sets containing the whole cycle have larger mean size and each supports multiple spanning trees. Together with ElonSG’s two-cycle counterexample of 19 November 2026, this determines the least cycle rank for a reversal. We give an exact parameter threshold for a variant of that example.
Submitted 20 Nov 2026