Trees & Spanning Trees
Trees & Spanning Trees
A tree is a connected acyclic graph. Trees are the sparsest connected graphs ($m=n-1$) and are fundamental in algorithms (decision trees, parse trees, search trees). The number of labeled trees on $n$ vertices is $n^{n-2}$ (Cayley's formula). Minimum spanning trees (MST) — subsets of edges that connect all vertices with minimum total weight — arise in network design; Kruskal's and Prim's algorithms find them greedily in $O(m\log n)$.
Trees & Spanning Trees
A tree is a connected graph with no cycles. Equivalent characterizations: (i) connected, $m=n-1$; (ii) acyclic, $m=n-1$; (iii) connected, any edge removal disconnects; (iv) any two vertices connected by a unique path. A spanning tree of $G$ is a subgraph that is a tree containing all vertices. Every connected graph has a spanning tree (remove edges from cycles). The number of spanning trees of $G$ equals any cofactor of the Laplacian $L=D-A$ (Matrix-Tree Theorem).
Cayley's Formula & Matrix-Tree Theorem
The number of labeled trees on $n$ vertices is $T_n=n^{n-2}$. Proof via Prüfer sequence: each labeled tree bijects with a sequence $(a_1,\ldots,a_{n-2})\in[n]^{n-2}$ (remove lowest-degree leaf, record its neighbor, repeat). The Matrix-Tree theorem: the number of spanning trees of $G$ equals $\det(L_{ii})$ (any $(n-1)\times(n-1)$ minor of the Laplacian $L$). Equivalently, $\frac{1}{n}\lambda_1\lambda_2\cdots\lambda_{n-1}$ where $\lambda_i$ are the nonzero eigenvalues of $L$.
Example 1
Find all labeled trees on $n=4$ vertices.
Solution: $T_4=4^2=16$. Via Prüfer: sequences in $\{1,2,3,4\}^2$: 16 sequences. Each corresponds to a unique tree. Representative structures: $P_4$ (path) appears 12 times in various labelings; $K_{1,3}$ (star) appears 4 times. Alternatively, up to isomorphism: only 2 trees on 4 vertices (path $P_4$ and star $K_{1,3}$), but labeled trees number 16.
Example 2
Apply Kruskal's algorithm to find the MST of a complete graph $K_4$ with edge weights $w(12)=1, w(13)=3, w(14)=5, w(23)=4, w(24)=2, w(34)=6$.
Solution: Sort edges: (1,2):1, (2,4):2, (1,3):3, (2,3):4, (1,4):5, (3,4):6. Add (1,2): no cycle. Add (2,4): no cycle. Add (1,3): no cycle (forest). Adding (1,4) would create 1-2-4... no, 1 connects to 2, 4 connects to 2, adding (1,3) connects component. MST edges: (1,2),(2,4),(1,3), total weight $1+2+3=6$.
Practice
- Prove: a graph is a tree iff it is connected with $m=n-1$.
- Describe Prim's algorithm and prove it finds the MST.
- Use the Matrix-Tree theorem to count spanning trees of $K_4$.
- Show every tree with $n\geq 2$ vertices has at least 2 leaves.
Show Answer Key
1. ($\Rightarrow$) A tree is connected and acyclic. Removing any edge disconnects it, so $m=n-1$ (induction on $n$). ($\Leftarrow$) Connected with $m=n-1$: if it has a cycle, removing a cycle edge keeps it connected with $m'=n-2 2. Prim's: start from any vertex, repeatedly add the cheapest edge connecting the tree to a non-tree vertex. Correctness: at each step, the chosen edge is the lightest crossing the cut $(S,V\setminus S)$. By the cut property, it must be in some MST. By induction, the result is an MST. 3. Matrix-Tree: the number of spanning trees equals any cofactor of the Laplacian $L=D-A$. For $K_4$: $L=\begin{pmatrix}3&-1&-1&-1\\-1&3&-1&-1\\-1&-1&3&-1\\-1&-1&-1&3\end{pmatrix}$. Cofactor = $\det$ of $3\times3$ minor $=16$. (Cayley's formula: $n^{n-2}=4^2=16$.) ✓ 4. Sum of degrees $=2(n-1)$ (tree has $n-1$ edges). If all vertices had degree $\ge2$, the sum would be $\ge2n>2(n-1)$ — contradiction. So $\exists$ a vertex of degree 1. Removing it gives a tree on $n-1$ vertices, which by the same argument also has a leaf. So $\ge2$ leaves.