3
$\begingroup$

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.

  • 0
    You can’t have something like '\$K_n\$' within a \text{...} block; view page source to see how I changed it.2011-08-23

1 Answers 1

3

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}$.