Mean Subtree Order in Graphs with One Cycle
Abstract
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.Discussion
Sign in to join the discussion.