Number of spanning trees containing a given forest

Abstract: We consider all spanning trees of a complete simple graph

G a m m a

on

n

vertices that contain a given

m -

forest

F

. We show that the number of such spanning trees,

a u (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,

a u (F) = q_{1} q_{2} c d o t s q_{m} n^{m - 2}

.

This page was built for publication: Number of spanning trees containing a given forest