I recently read the answer to a question regarding the difference between a tree and a spanning tree. The following is the link: Difference between a tree and spanning tree?!
Now we know that the total possible trees for a graph = n^(n-2). Therefore, for a graph containing 4 nodes, number of trees possible = 4^(4-2) = 16
Graph and all of its possible trees
Looking at the picture, it is clear that all of the 16 trees contain all 4 nodes present in the original graph, i.e. there is not a single tree with less than 4 nodes. But the answer provided in the question to the link shared above says otherwise. I am pretty confused by now. Any response would be greatly appreciated.
In order to close the topic :
Cayley's formula counts the number of labelled trees on $n$ vertices, hence of spanning tree of $K_n$ ( the complete graph on $n$ vertices).
Cayley's formula does not count all possibles trees, the spanning tress of subgraphs of $K_n$. If you want to do count this, then you need to iterate through all subgraphs of $K_n$ : Counting the number of labelled spanning trees of each $K_{n-k}$, multiplied by the number of labelled $K_{n-k}$:
$$ T = \sum_{k=0}^{n-1} \binom{n}{k} (n-k)^{n-k-2} $$ I don't know if this sum can be simplified.