Take the 2-minute tour ×

EDIT: I think everyone understood, but I never explicitly stated that I am looking at labeled spanning trees.

Let $T$ be a tree contained in $K_n$ (the complete graph on $n$ vertices). How can one compute (or at least bound) the size of the set $$ \{S \mid S \text{ a labeled spanning tree of } K_n, T \not\subseteq S \}? $$

If we aren't interested in avoiding any tree, then Cayley's formula gives $n^{n-2}$ spanning trees of $K_n$. Thus, we could alternatively ask for the size of the set $$ \{S \mid S \text{ a labeled spanning tree of }K_n, T \subseteq S \} $$ and subtract.

More generally, I would be interested in solving the problem for avoiding a forest contained in $K_n$, but perhaps this can be deduced from the case of a tree via inclusion-exclusion.

share|improve this question
You can’t have something like '\$K_n\$' within a \text{...} block; view page source to see how I changed it. –  Brian M. Scott Aug 23 '11 at 2:09
add comment

1 Answer

up vote 3 down vote accepted

Suppose $T$ contains $k$ vertices. Any spanning tree $S$ of $K_n$ containing $T$ can be converted to a spanning tree $S'$ of $K_{n-k+1}$ by contracting $T$. Going in the opposite direction, we can replace a vertex of degree $d$ in $K_{n-k+1}$ by $T$ in $kd$ ways. Since the average degree of a given vertex in a spanning tree of $K_{n-k+1}$ is $2\frac{n-k}{n-k+1}$, there are $2Nk\frac{n-k}{n-k+1}$ of the desired spanning trees containing $T$, where $N$ is the number of spanning trees of $K_{n-k+1}$.

share|improve this answer
add comment

Your Answer


