# Graph Theory - Trees

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.

• A tree is connected. The formula for counting trees on 4 vertices (nodes) counts exactly that: the trees that contain exactly 4 nodes. A subgraph does not have to contain all nodes of the original graph, so can still possibly be a tree without containing all the vertices of the original. – Morgan Rodgers Jan 21 at 19:02
• Cayley's formula says that there are $n^{n-2}$ labeled trees on $n$ vertices, i.e. each of those trees must contain all $n$ vertices, hence they would span the complete graph. I think you have a misunderstanding of this formula, especially because I'm not sure what you mean by the "total possible trees for a graph". If you mean subgraphs which are trees, then Cayley's formula does not count that. – Kevin Long Jan 21 at 19:32

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.