What is the total number of spanning trees on all subsets of vertices in a complete graph?

Question

On a complete graph with $n$ vertices, I need to find the total number of spanning trees on every subset of vertices. The number of subsets in the graph is $2^n$. Cayley's formula $k^{k-2}$ then applies to each subset but I suppose I would need to know the number of vertices $v$ for each subset such that $k = n-v$.

Answer 1

Since you want to count sum of the number of spanning trees for each subgraph of $K_n$, you need to:

1- list all possible subgraphs

2- compute the number of spanning tree for each of these.

As you said, the number of spanning trees of the subgraphs of the complete tree depends only on the number of vertices chosen, since the subgraph are themselves complete, and is $k^{k-2}$ (where $k$ is the number of vertices of the subgraphs), except for $k=1$ where this number is $1$.

Then if you put $c(k)$ the number of way to chose $k$ vertices among $n$, then the answer to your question should be $\sum_{k=1}^{n}c(k)k^{k-2}$.

Now $c(k)$ is a well-known function, $c(k)={n\choose k}={n! \over k!(n-k)!}$ (see https://en.wikipedia.org/wiki/Binomial_coefficient). So the answer is $ {n\choose 1} + \sum_{k=2}^{n}{k\choose n}k^{k-2}$.

See also https://oeis.org/A270593 for the first terms of this sequence and context.