Counting the Number of Trees¶
Counting the number of \(n\)-vertex trees is one of the most fascinating problems in combinatorics, with various creative approaches existing for it. In this section, the discussion focuses on trees with labeled vertices. (You can consider them as the number of spanning subgraphs of the graph \(K_n\)). We will in fact prove through several methods that the number of \(n\)-vertex trees is \(n^{n-2}\). Before reading the solution to each part, review the hints and attempt to devise your own approach.
Counting with Degree Sequences¶
def make_adjacency_matrix(n, edges):
%% This function constructs an adjacency matrix for a graph
matrix = [[0]*n for _ in range(n)]
for u, v in edges:
matrix[u][v] = 1
matrix[v][u] = 1 # For undirected graphs
return matrix
The degree sequence of a graph is a list of vertex degrees arranged in non-increasing order. Two graphs with the same degree sequence are said to be degree-equivalent, though they may not necessarily be isomorphic. This sequence plays a key role in the Erdős–Gallai theorem for characterizing graphical sequences.
Hint¶
Provide a relation that counts the number of trees with the degree sequence \(d_1, d_2, ..., d_n\). To prove this relation inductively, we remove a leaf!
Solution¶
The desired formula is \(\frac {(n-2)!} {(d_1-1)! \times (d_2-1)! \times \cdots \times (d_n-1)!}\) . Note that \(\sum (d_i-1)\) equals \(n-2\), meaning the above expression is essentially a multinomial coefficient!
To prove the formula, use induction on \(n\). For the base case, consider \(n \leq 2\) where the formula holds. Now consider a specific leaf vertex (a vertex \(u\) with \(d_u = 1\)). Enumerate cases based on which vertex is adjacent to \(u\). If the only neighbor of \(u\) is vertex \(v\) (note that since \(n > 2\), \(v\) cannot be a leaf), then the number of possible trees in this case equals \(\frac {(n-2)!} {(d_1-1)! \times (d_2-1)! \times \cdots \times (d_v-2)! \times \cdots \times (d_n-1)!}\) . As stated, this expression resembles a multinomial coefficient. According to the generalized Pascal's identity, the sum of all such terms (after enumerating cases) will equal \(\frac {(n-2)!} {(d_1-1)! \times (d_2-1)! \times \cdots \times (d_n-1)!}\) , which is exactly what we wanted.
Now observe that this formula effectively counts the number of distinct sequences containing character \(i\) exactly \(d_i-1\) times. This is equivalent to assigning each tree to an \(n-2\) length sequence of numbers from \(1\) to \(n\). Therefore, summing over all possible degree sequences \(d_1,d_2,...,d_n\) yields \(n^{n-2}\) - the total number of distinct \(n\)-vertex trees.
Proof Code¶
In this section, we implement an algorithm to generate a random graph with n nodes and a specified number of edges. The code uses the NetworkX library to create and visualize the graph.
import networkx as nx
import matplotlib.pyplot as plt
# Set the number of nodes
n = 10
# Create an empty graph
G = nx.Graph()
# Add nodes to the graph
G.add_nodes_from(range(n))
# Calculate initial edges based on degree
for i in range(n):
# Connect each node to its next neighbor
G.add_edge(i, (i+1) % n)
# Draw the graph
nx.draw_circular(G, with_labels=True)
plt.show()
The above code first creates a cyclic graph by connecting each node to its subsequent neighbor. Then, additional edges are added randomly until the total number of edges reaches the desired value.
In the next chapter, we will discuss algorithms for detecting connected components in graphs.
Guidance¶
We establish a one-to-one correspondence between \(n\)-vertex trees and sequences of length \(n-2\) consisting of numbers from \(1\) to \(n\).
1print([1]) # This method can also be written manually
Solution¶
Our correspondence function operates as follows: initially, we consider the tree \(T\). While the number of its vertices is greater than 2, we repeatedly remove the leaf \(u\) with the minimal label. Then we write down the label of the only adjacent vertex \(u\) on paper. Finally, consider the \(n-2\) numbers we wrote on paper in the order they were recorded. These form our \(n-2\) sequence.
To prove the bijectiveness of the correspondence, we must show that every \(n-2\)-length sequence of numbers from \(1\) to \(n\) uniquely corresponds to an \(n\)-vertex tree. Consider the sequence \(s_1,s_2,...,s_{n-2}\). We aim to reconstruct the corresponding tree.
First, note that in the correspondence process, vertex \(i\) appears exactly \(d_i-1\) times in the sequence (why?).
Thus, numbers not appearing in \(s_1,s_2,...,s_{n-2}\) must be leaves of the tree. In the correspondence process, we first removed the leaf with the minimal label. Let \(u\) be the smallest number not present in \(s_1,s_2,...,s_{n-2}\). Initially, \(u\) must have been removed, and its only adjacent vertex is \(s_1\). Now, we can inductively construct the tree corresponding to \(s_2,...,s_{n-2}\). By adding the edge \((u,s_1)\) to this tree, we obtain the tree corresponding to \(s_1,s_2,...,s_{n-2}\).
Guidance¶
A two-colored tree is defined as a tree where vertex \(A\) is colored blue and vertex \(B\) is colored red (even if \(A\) and \(B\) are the same vertex).
It is clear that for every \(n\)-vertex tree, there are exactly \(n^2\) two-colored trees. Therefore, if we have \(c\) distinct \(n\)-vertex trees, then there are \(c \times n^2\) two-colored \(n\)-vertex trees.
In this section, we establish a one-to-one correspondence between \(n\)-vertex functional graphs (whose count is \(n^n\)) and two-colored trees.
Solution¶
Consider a functional graph. As you know, in a functional graph, each connected component (in the underlying graph) consists of a directed cycle from which an arborescence (pendant tree) hangs from each vertex. Intuitively, to convert this functional graph into a tree, it suffices to remove one edge from each cycle and then connect the connected components of the functional graph to form a tree. However, this process must be done in a way that establishes a bijection, allowing us to determine which edge was removed based on the bicolored tree!
Assume for each connected component of the functional graph (in the underlying graph), we call the smallest label in its cycle the beauty of the component, and the vertex with this minimal label the beautiful vertex of the component. Now, perform the following correspondence process:
Sort the components from left to right such that their beauties are in descending order.
For each component, suppose its cycle is \(p_1,p_2,...,p_k\) where \(p_1\) is the beautiful vertex of the component. First, remove the edge \(p_kp_1\). Then, connect \(p_k\) to the beautiful vertex of the next component (to the right).
Color the vertex \(p_1\) in the leftmost component blue and the vertex \(p_k\) in the rightmost component red. Then, remove all edge directions.
This constructs a bicolored tree from the original functional graph.
Why did we define the beauty of a component as the *smallest* vertex in its cycle, and why did we sort components in *descending* order of beauty? The sole reason is to ensure the path from the blue vertex to the red vertex satisfies a property we call the attractive property.
Attractive Property: First, note that each cycle in the original functional graph now corresponds to a segment of the path between the blue and red vertices. Starting from the blue vertex and moving toward the red vertex, observe the labels. Suppose we are at vertex \(u\), and the smallest label seen before \(u\) along the path is \(X\). If \(u < X\) (i.e., \(X\) decreases after this step), it means we have entered a vertex belonging to another cycle (from the original functional graph). (Why?)
To prove the correspondence is reversible, we must uniquely reconstruct the functional graph from a given bicolored tree.
As mentioned, let the blue vertex be \(A\) and the red vertex be \(B\).
We reverse the correspondence steps to recover the functional graph:
Hang the tree along the path from \(A\) to \(B\). Place \(A\) on the left and \(B\) on the right.
The path \(A-B\) must be directed from left to right.
All subtrees hanging from vertices on the \(A-B\) path must be directed from bottom to top (each vertex has an edge to its parent).
Using the attractive property, we partition the path into segments that originally belonged to the same component in the functional graph. Each segment was a cycle with vertices \(p_1,...,p_k\), where the edge \(p_kp_1\) was removed. Thus, we add an edge from the last vertex of the segment (\(p_k\)) to the first vertex of the segment (\(p_1\)).
By reversing the correspondence steps, we uniquely reconstruct the functional graph from any bicolored tree. This proves the bijection.
Counting Branches¶
To determine the number of branches in a graph, we can use the following approach. A branch is defined as a vertex with a degree greater than two. The process involves calculating the degree of each vertex and counting how many exceed this threshold.
def count_branches(graph):
# Calculate the degree of each vertex
degrees = [len(graph[node]) for node in graph]
# Branches are the number of vertices with degree more than two
return sum(1 for deg in degrees if deg > 2)
For example, in the graph below, vertices A, C, and D have degrees 3, 4, and 3, respectively. Thus, the number of branches is 3.
This method efficiently counts branches by iterating through each node once, resulting in a time complexity of O(n), where n is the number of vertices.
Guidance¶
We try to count the number of arborescences (rooted trees where each vertex except the root has a directed edge to its parent). Additionally, assume the edges of the tree have an order, meaning we have an \(n-1\)-permutation written on the tree's edges.
In this case, if the number of counted arborescences (considering edge order) equals \(T\), then the number of trees will be \(\\frac {T} {(n-1)! \\times n}\). In other words, each tree is counted \((n-1)! \\times n\) times. The coefficient \(n\) accounts for the root selection in the tree, and \((n-1)!\) accounts for the permutation ordering written on the tree's edges.
Solution¶
We attempt to compute \(T\). Consider a specific spanning tree and model its construction process as follows:
Start with a graph of \(n\) vertices and no edges. Add edges one by one. At each step, we will have several directed trees.
At step \(i\), consider the edge labeled \(i\). Let it be \(uv\).
It is necessary and sufficient that at each step, \(u\) and \(v\) belong to different components, and \(v\) is the root of one of our directed trees.
To count the number of possible spanning trees, it suffices to determine how many different paths the construction process can take.
At the start of step \(i\) (counting from 1), there are exactly \(n-i+1\) rooted trees. If we consider choices for \(u\) (which has \(n\) options), there are exactly \(n-i\) choices for \(v\) because \(v\) must be the root of one of the trees and cannot be in the same tree as \(u\). Thus, step \(i\) in the graph construction process has \(n \times (n-i)\) possible states. Ultimately, we have: \(T = n^{n-1} \times (n-1)!\)
Therefore, as we stated earlier, the number of trees must equal \(\frac {T} {(n-1)! \times n}\), which simplifies to \(n^{n-2}\). Exactly as desired!
This book is made by The Shaazzz contributors.
It is publicly available with cc-by-sa license.
Last updated at آوریل 19, 2025.
Rendered by Sphinx (4.3.2) and Minoo theme (Beta 0.9.7).
