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$.
The total number of spanning trees on all subsets of vertices in a complete graph
combinatoricsgraph theorytrees
Related Solutions
Cayley's formula counts all labeled trees of order $n$. In your case, this includes trees that use the edge $\{1,4\}$, which is absent from the graph you posted.
(As for why the overcount is exactly a factor of $2$: with $6$ possible edges among the four vertices and $3$ edges in every tree on $4$ vertices, you should expect every possible edge to show up in exactly half the labeled trees, so exactly half of the possible labeled trees counted by Cayley's formula will contain the edge $1,4$.)
A wheel with $n$ vertices is a cycle $C_{n-1}$, joined to a single vertex $v$. Label the vertices of this cycle $u_1, u_2, \dots, u_{n-1}$.
Let the first spanning tree $T_1$ be the path $(v, u_1, u_{n-1}, u_{n-2}, \dots, u_2)$. Let the second spanning tree $T_2$ be the 'star' centered at $v$, with edges $vu_2, vu_3, \dots, vu_{n-1}$, as well as the single edge $u_1u_2$ of the cycle.
In the diagram below, $T_1$ is blue, and $T_2$ is red.
Best Answer
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.