Chainsawing Cayley Trees: Markovian Methods in Tree Enumeration
Nubar Qocayeva · Luminis Applied Science and Engineering · 2025
We revisit Cayley’s classical result that there are nn−2 labeled trees on nn vertices (Cayley’s formula). We introduce a stochastic pruning process on this space of Cayley trees, which we term a Markov chainsaw. In this model, edges of a labeled tree are cut or reattached randomly over time, yielding a Markov chain on the space of forests. We derive rigorous results for this process: we prove it is irreducible and aperiodic on the forest state space, and we find its stationary distribution via detailed balance. In particular, the uniform spanning-tree case recovers Cayley’s count and relates to loop-erased random walks and Wilson’s algorithm. We also implement computational experiments (in Python/NetworkX) for small nn to illustrate convergence and mixing; empirical frequencies agree with our theoretical stationary laws. Our contributions tie together classical enumeration (e.g. Prüfer codes), Markov‐chain theory (coupling and convergence), and applications in random graph processes and network reliability.