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.

$\endgroup$
  • $\begingroup$ You can’t have something like '\$K_n\$' within a \text{...} block; view page source to see how I changed it. $\endgroup$ – Brian M. Scott Aug 23 '11 at 2:09
3
$\begingroup$

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

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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