Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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

1 Answer 1

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

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.