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.

  • $\begingroup$ 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. $\endgroup$ – Morgan Rodgers Jan 21 at 19:02
  • 2
    $\begingroup$ 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. $\endgroup$ – Kevin Long Jan 21 at 19:32

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.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.