Number of spanning trees containing a given forest

Peter J. Cameron; Michael Kagan

paper

Number of spanning trees containing a given forest

arXiv:2210.09009

Abstract

We consider all spanning trees of a complete simple graph $Γ$ on $n$ vertices that contain a given $m -$ forest $F$ . We show that the number of such spanning trees, $τ (F)$ , doesn't depend on the structure of $F$ and is completely determined by the number of vertices $q_{i} (i = 1, ..., m)$ in each connected component of $F$ . Specifically, $τ (F) = q_{1} q_{2} \dots q_{m} n^{m - 2}$ .

Version 2, 3 pages