Counting the number of labeled trees

In this blog, we’ll talk about labeled trees and the counting the total number of labeled trees in a graph with n vertices.

A labeled tree is one in which all the vertices are assigned a label or a name. For simplicity, we will label these $n$ vertices from the set ${1, 2, 3, \cdots, n}$.

A labeled tree, or a labeled graph, is different from its unlabeled counterparts because all the nodes in labeled graphs represent some concrete element—people on social media, or classes or objects in a particular software—and the edges between them correspond to their interaction.

Let’s have a look at some of the labeled trees.

For $n = 2$, there is only one possible tree, which is shown below.

For $n = 3$, there are three possible trees, which are shown below.

In the above image, all three images look the same, but if we look at their labels, we will notice a difference—the label of the vertex in the center is different in all three of them, so they are counted as three different trees. If the trees were unlabeled, we would have considered them the same tree.

Just to observe the difference, have a look at an unlabeled tree and some graphs that are not trees, and some unlabeled trees.

One-to-one functions#

In this blog, our goal is to derive a formula for the number of trees with $n$ labeled vertices. But before discussing labeled trees, let’s talk about one-to-one functions.

The above diagram represents the function $f(x) = 5$ – $x$. This function takes input from the domain (shown on the left-hand side) and maps it to the elements of the co-domain (shown on the right-hand side). The mapping between the inputs and outputs of the function is shown by connecting them through the arrows. If none of the elements on the right-hand side have incoming arrows from multiple inputs, then the corresponding function is said to be one-to-one.

Every domain element is paired with a distinct element from the co-domain for any one-to-one function. This indicates that the number of elements between the two sets is the same for such functions. In some cases, some elements of the co-domain might not have a corresponding element from the domain. Here, the cardinalityCardinality of a set is the number of elements present in that set of the domain will be less than the cardinality of the co-domain. An example is shown below.

The diagram above represents the one-to-one function $f(x) = x + 1$ from the domain $\{1, 2, 3\}$ to the co-domain $\{1, 2, 3, 4\}$. Here, the cardinality of the domain is less than the cardinality of the co-domain.

Are two sets equal?#

Suppose we have a function, $f:A \rightarrow B$. This notation tells us that the function $f$ maps elements from domain $A$ to the co-domain $B$. If this function is one-to-one, then $|A| \le |B|$.

Suppose there is another one-to-one function, $g: B \rightarrow A$. This implies that $|B| \le |A|$.

If for any pair of sets $A$ and $B$, we can find two functions $f$ and $g$ as described above, we can conclude that the two sets have the same cardinality, i.e., $|A| = |B|$.

The counting process#

Let’s first look at the outline of the steps before getting into the details.

We are interested in counting the labeled trees. We will define set $A$ that contains all trees with $n$ vertices. We will define another set, $B$, whose elements can be counted easily.

Next, we will relate these two sets by using two one-to-one functions $f$ and $g$, as described below.

$f: A \rightarrow B$

$g: B \rightarrow A$

The sets and the functions#

Continuing the discussion, we define set $A$ as the set of labeled trees of size $n$ and set $B$ as the set of arrays of size $n$ – $2,$ containing elements from the set $\{1, 2, 3, ... , n\}.$ The function $f$ will map elements of set $A$ to elements of the set $B$. The function $g$ will map elements from set $B$ to the elements of set $A$.

Set A#

This set consists of labeled trees. Each tree will contain $n$ vertices, and each vertex will be assigned a label from the set $\{1, 2, 3, \cdots, n\}$. No two vertices will be assigned the same label. Let’s recall that we want to find out the cardinality of this set.

Set B#

Each item of this set is an array of size $n$ – $2$. The elements of this array are from the set $\{1, 2, 3, \cdots, n\}$. For $n = 3$, we have the following arrays of size $1$.

We want to relate this set with set A using one-to-one functions $f$ and $g$.

Let’s discover these functions one at a time.

The function fff#

The function $f$ is a function from set $A$ to set $B$. In simpler words, we want to store the information of a labeled tree with $n$ vertices in an array of size $n$ – $2$. We will demonstrate how to do that in the next section.

Recall that this function will take a tree as an input and return an array at the output. Using this function, we want to relate the number of labeled trees and the number of arrays of corresponding size. An example of the labeled trees with three vertices is shown below.

Let’s look at the steps of this function in the pseudocode below. An example will follow afterward.

Algorithm for fff#

Input: A tree with $n$ vertices

Output: An array $E$ of size $n-2$

1. Construct an array E of size $n-2$

2. FOR $(i = {1, 2, \cdots, n-2})$

3. $\hspace{3em} x =$ the smallest leaf vertex

4. $\hspace{3em} y =$ neighbor of $x$

5. $\hspace{3em} E[i] = y$

6. $\hspace{3em}$DELETE vertex $x$ from the tree

Example for fff#

Below is an example with $6$ vertices.

This array is also called the Prüfer code. The Prüfer code for the graph discussed in the above example is $[4, 1, 1, 4].$

The function ggg#

The function $g$ is a function from set $B$ to set $A$. This function takes an element from the set of arrays and maps it to an element from the set of labeled trees. In fact, the function we will discuss here is the inverse of the function $f$.

Again, we will look at the steps of this function before applying the steps to a concrete example.

Algorithm for ggg#

Input: An array Prüfer_Code of size $k$

Output: A labeled tree of size $k+2$

1. Create a list missing_Numbers

2. Create a graph G with the vertex set $V = \{1, 2, \cdots, k\}$

3. FOR $(i = {1, 2, \cdots, k})$

4. $\hspace{3em}$IF ($i$ is missing from the array Prüfer_Code)

5. $\hspace{3em}\hspace{3em}$INSERT $i$ in the list missing_Numbers

6. FOR $(i = {1, 2, \cdots, k-2})$

7. $\hspace{3em} x =$ minimum number in list missing_Numbers

8. $\hspace{3em}$ADD EDGE between the vertices $x$ and Prüfer_Code[$i$]

9. $\hspace{3em}$DELETE $x$ from the list missing_Numbers

10. $\hspace{3em}$IF (element Prüfer_Code[$i$] is not present in the Array between the indexes $i+1$ and $k$)

11. $\hspace{3em}\hspace{3em}$INSERT Prüfer_Code[$i$] in the list missing_Numbers

12. ADD EDGE between the two remaining elements of the list missing_Numbers

Example of function ggg#

Let’s visualize this algorithm with the help of an example. This function takes an array at the input and produces a tree at the output.

The final calculation#

The functions $f$and $g$ are both one-to-one. Moreover, these functions are the inverse of each other. The function $f$ takes a tree and maps it to an array, whereas the function $g$ takes the array and maps it back to the tree. This can be seen from the provided example. The same arrays and trees are used in these examples. This implies that the cardinality of both sets are equal.

Set $B$ is an array of size $n-2.$ For each entry, there are $n$ possible options, so the total number of such arrays is $n^{n-2}.$

This shows that the number of labeled trees with $n$ vertices is $n^{n-2}.$

Applications#

A graph with $n$ vertices requires $O(n^2)$ storage size if we want to save it in an adjacency matrix. Alternately, for a tree with $n$ vertices, we would require $2\times(n-1)$ space if we want to save the information of the edges. Recall that each edge is connected to $2$ vertices, and a tree has $n-1$ edges.

With this method, we can store a tree using an array of size $n-2.$ This is the best possible compression we can get if we want to store trees.

If you are interested in learning more about counting, graph theory, or sets, feel free to explore the following Educative courses.