Given a labelled clique $G=(E,V)$, I would like to enumerate the number of trees that can be made for a given number of edges $e$, such that the all nodes in the tree are connected.
For instance, let $G$ be the 4-clique graph. I would like to find the number of trees with 3 edges that can be formed as subgraphs.
I have tried to research this, but couldn't really get to grips with the literature. This MSE post looks very similar to my question, but I am struggling with the answer.
Here is my attempt at this problem. Firstly we calculate the total number of ways of selecting 3 edges from the 4-clique. There are 6 edges in total. There are $6\cdot 5 \cdot 4 = 120 $ different ways to make the choices; however, a lot of these are equivalent to one another. In fact, given any three choices of edge, $\{e_1,e_2,e_3\}$, the order that they are picked does not matter. So we must divide 120 by the number of permutations of a 3 letter word, which is 6. Hence, the number of graphs that can be made from the choice of any 3 edges from a 4-clique is $120/6= 20$ which is also the binomial coefficient
$$
\binom{6}{3}
$$
The number of trees must of course be less than this number. My naive approach is to think that a tree of size 3 will always contain 4 nodes. Research has shown that there are 16 such trees in the case of the 4 clique by employing
$$
n^{n-2}=4^2=16
$$
However, this method is only valid in this case. For larger cliques, how can I find the number of trees with $e$ edges, where $e\neq n-1$?
The particular case of $e=3$ is my main objective for arbitrary $n$.
Best Answer
A tree with $e$ edges has $e+1$ nodes. Given a set of $n$ nodes, there are $\binom n{e+1}$ ways to choose the set of nodes for the tree, and then by Cayley's formula there are $(e+1)^{e-1}$ trees on that set of nodes, so the final answer is $$\binom n{e+1}(e+1)^{e-1}.$$