Counting Labeled Tree

1 min read

Expression can be used to obtain the number of simple labeled graphs of n vertices and n – 1 edges. Some of these are going to be trees and others will be unconnected graphs with circuits.
For example, In Figure 6.2 below are all the 16 labeled trees with 4 points. The labels on these trees are understood to be as in the first and last trees shown.
We note that among these 16 labeled trees, 12 are isomorphic to the path P4 and 4 to k1, 3. The order of Γ(P4) is 2 and that of Γ(k1, 3) is 6.

We observe that since P = 4 here, we have

The expected generalization of these two observations holds not only for trees, but also for graphs, digraphs, and so forth.