Trees and Spanning Trees

What is a Tree?

In graph theory, a tree is a connected graph that contains no cycles. This simple definition gives rise to a set of powerful and equivalent properties. For any graph $G$ with $n$ vertices, the following statements are equivalent:

• $G$ is a tree.
• $G$ is connected and has exactly $n-1$ edges.
• $G$ is acyclic and has exactly $n-1$ edges.
• There is a unique simple path between any two vertices in $G$.
• $G$ is minimally connected: if you remove any single edge, the graph becomes disconnected.
• $G$ is maximally acyclic: if you add any single edge between two non-adjacent vertices, a cycle is created.

Trees are the backbone of many algorithms and data structures, from the file systems on your computer to decision trees in machine learning. Their property of providing a unique path between any two nodes with the minimum number of edges makes them exceptionally efficient.

Spanning Trees: The Skeleton of a Graph

Most graphs you encounter in problems are not trees themselves because they contain cycles. However, within any connected graph, we can find a "skeletal" version that is a tree. This is called a spanning tree.

A spanning tree of a connected graph $G$ is a subgraph of $G$ that:

1. Is a tree.
2. Includes all the vertices of $G$.

Think of it as finding the most economical way to connect all cities in a transport network. You need enough roads to ensure everyone is connected, but no extra roads that create redundant loops. For any connected graph, there can be multiple, often many, spanning trees.

The following video provides a great visual introduction to this idea.

Counting Spanning Trees: Kirchhoff's Matrix Tree Theorem

While listing out all spanning trees is feasible for a tiny graph, it quickly becomes impossible for larger, more complex graphs. For GATE, you need a systematic, algorithmic approach. This is provided by Kirchhoff's Matrix Tree Theorem.

The theorem uses a special matrix representation of the graph called the Laplacian matrix. The number of spanning trees is then found by calculating a determinant. Let's break down the procedure.

Steps to apply Kirchhoff's Theorem:

1. Construct the Adjacency Matrix ($A$):
   This is an $n\times n$ matrix where $A_{ij}=1$ if there is an edge between vertex $i$ and vertex $j$, and $0$ otherwise. For simple graphs, the diagonal entries $A_{ii}$ are 0.

2. Construct the Degree Matrix ($D$):
   This is an $n\times n$ diagonal matrix where the entry $D_{ii}$ is the degree of vertex $i$, and all off-diagonal entries are $0$.

3. Form the Laplacian Matrix ($L$):
   The Laplacian is defined as $L=D-A$.

   • The diagonal entries $L_{ii}$ will be the degree of vertex $i$.
   • The off-diagonal entries $L_{ij}$ will be $-1$ if an edge exists between $i$ and $j$, and $0$ otherwise.
   • A key property is that all rows and columns of the Laplacian matrix sum to zero.

4. Calculate a Cofactor:
   Choose any row $i$ and any column $j$ and delete them to create an $(n-1)\times (n-1)$ submatrix. This submatrix is called a cofactor. A common choice is to remove the first row and first column.

5. Find the Determinant:
   The number of spanning trees of the graph $G$ is the determinant of this $(n-1)\times (n-1)$ cofactor matrix. The theorem guarantees that the result will be the same no matter which row and column you choose to delete.

The next segment of the video you just watched walks through this exact procedure with the graph from the introduction.

For your B.Tech in IT, you are already familiar with matrices and determinants. The main new concept here is the construction of the Laplacian matrix and the surprising fact that its cofactors' determinants count something as combinatorial as spanning trees. This is a powerful and very testable procedure.

A Special Case: Complete Graphs and Cayley's Formula

What if we need to find the number of spanning trees for a complete graph $K_n$, where every vertex is connected to every other vertex? We could use Kirchhoff's theorem, but it would involve calculating the determinant of a large $(n-1)\times (n-1)$ matrix.

Fortunately, there is a famous and beautiful shortcut known as Cayley's Formula.

Cayley's Formula: The number of spanning trees in a complete graph $K_n$ is $n^{n-2}$.

This formula also answers a related question: "How many distinct labeled trees are there with $n$ vertices?" Since any labeled tree on $n$ vertices is a spanning tree of the complete graph $K_n$, the answer is the same.

Example:

• For $K_4$, the number of spanning trees is $4^{4-2}=4^2=16$.
• For $K_5$, the number of spanning trees is $5^{5-2}=5^3=125$.

The final part of the video explains how this formula is connected to Kirchhoff's Theorem.

Problem-Solving Strategy for GATE:
When a question asks for the number of spanning trees:

1. Check the graph type: Is it a general graph or a complete graph $K_n$? (A question about "all labeled trees on n vertices" implies $K_n$).
2. If it's $K_n$, use Cayley's Formula: $n^{n-2}$. This is a fast, direct calculation.
3. If it's any other graph, use Kirchhoff's Matrix Tree Theorem: build $L=D-A$, find a cofactor, and compute its determinant.

Conclusion

In this lesson, we focused on trees and their role as the fundamental building blocks of connected graphs. You learned the essential properties of trees and the definition of a spanning tree. Most importantly, you acquired two algorithmic methods for counting spanning trees—a common task in GATE.

Key Takeaways:

• A tree is a connected acyclic graph with $n$ vertices and $n-1$ edges.
• A spanning tree is a subgraph that connects all vertices of the original graph without forming any cycles.
• Kirchhoff's Matrix Tree Theorem provides a universal algorithm for counting spanning trees in any graph by calculating the determinant of a cofactor of the Laplacian matrix ($L=D-A$).
• Cayley's Formula ($n^{n-2}$) is a powerful shortcut for the special case of complete graphs ($K_n$) or, equivalently, for finding the total number of labeled trees on $n$ vertices.

In our next lesson, we will continue exploring subgraph structures by investigating Graph Matching. We'll focus on bipartite graphs and tackle problems related to finding the maximum number of independent edges, a concept with wide-ranging applications in assignment and scheduling problems.