Spanning Trees

Spanning trees are special subgraphs of a graph that have several important properties. First, if T is a spanning tree of graph G, then T must span G, meaning T must contain every vertex in G. Second, T must be a subgraph of G. In other words, every edge that is in T must also appear in G. Third, if every edge in T also exists in G, then G is identical to T.

Spanning trees are important in path-finding algorithms such as Dijkstra's shortest path algorithm and A* search algorithm. Spanning trees are calculated as sub-parts in those algorithms. It is also used in network routing protocols. The spanning tree protocol is one example.

Graph with a spanning tree highlighted in blue ^[1]

There are a few general properties of spanning trees.

1. A connected graph can have more than one spanning tree. They can have as many as \(|v|^{|v|-2},\) where \(|v|\) is the number of vertices in the graph.
2. All possible spanning trees for a graph G have the same number of edges and vertices.
3. Spanning trees do not have any cycles.
4. Spanning trees are all minimally connected. That is, if any one edge is removed, the spanning tree will no longer be connected.
5. Adding any edge to the spanning tree will create a cycle. So, a spanning tree is maximally acyclic.
6. Spanning trees have \(|n| - 1\) edges, where \(|n|\) is the number of vertices.

Different types of graphs have different numbers of spanning trees. Here are a few examples.

1) Complete Graphs

A complete graph is a graph where every vertex is connected to every other vertex. The number of spanning trees for a graph G with \(|v|\) vertices is defined by the following equation: \(T(G_\text{complete}) = |v|^{|v|-2}\).

Complete Graph^[2]

2) Connected Graphs

For connected graphs, spanning trees can be defined either as the minimal set of edges that connect all vertices or as the maximal set of edges that contains no cycle.

A connected graph is simply a graph that necessarily has a number of edges that is less than or equal to the number of edges in a complete graph with the same number of vertices. Therefore, the number of spanning trees for a connected graph is \(T(G_\text{connected}) \leq |v|^{|v|-2}\).

Connected Graph^[3]

3) Trees

If a graph G is itself a tree, the only spanning tree of G is itself. So a tree with \(|v|\) vertices is defined as \(T(G_\text{tree}) = |v|^{|v|-2}\).

Tree Graph^[4]

4) Complete Bipartite Graph

A bipartite graph is a graph where every node can either be associated with one of two sets, \(m\) or \(n\). Vertices within these sets only connect to vertices in the other. There are no intra-set edges. A complete bipartite graph then is a bipartite graph where every vertex in set \(m\) is connected to every vertex in set \(n\), and vice versa.

The number of spanning trees for a bipartite graph is defined by \(T(G_\text{complete-bipartite}) = m^{n-1} \cdot n^{m-1}\).

Complete Bipartite Graph^[5]

5) General Graph

To calculate the number of spanning trees for a general graph, a popular theorem is Kirchhoff's theorem.

To perform this theorem, a two-dimensional matrix must be constructed that can be indexed via both row and column by the graphs' vertices. The cell in the \(i^\text{th}\) row and \(j^\text{th}\) column has a value that is determined by three things. If \(i = j\), then the value in the cell will be equal to the degree of \(i\). If \(i\) and \(j\) are adjacent, then the value will be \(-1\). Otherwise, the value will be \(0\).

From here, an arbitrary vertex is chosen and its corresponding row and column is removed from the matrix. The determinant of this new matrix is a spanning tree \(T(G)\).

Spanning trees can be found in linear \(O(V + E)\) time by simply performing breadth-first search or depth-first search. These graph search algorithms are only dependent on the number of vertices in the graph, so they are quite fast.

Breadth-first search will use a queue to hold vertices to explore later, and depth-first search will use a stack. In either case, a spanning tree can be constructed by connecting each vertex \(v\) with the vertex that was used to discover it.

Unfortunately, these search algorithms are not well suited for parallel or distributed computing, an area in which spanning trees are popular. There are, however, algorithms that are designed to find spanning trees in a parallel setting.

For complete graphs, there is an exact number of edges that must be removed to create a spanning tree. For a complete graph G, a spanning tree can be calculated by removing \(|e| - |v| + 1\) edges. In this equation, \(|e|\) is the number of edges, and \(|v|\) is the number of vertices.

Minimum spanning trees are a variant of the spanning tree.
A minimum spanning tree for an unweighted graph G is a spanning tree that minimizes the number of edges or edge weights.
A minimum spanning tree for a weighted graph G is a spanning tree that minimizes the weights of the edges in the tree.

These two images show the difference between a spanning tree and minimum spanning tree. The edges that are grayed out are left out of their respective trees, but they're left in the images to show their weights.

Weighted spanning tree

Weighted minimum spanning tree

Minimum spanning trees are very helpful in many applications and algorithms. They are often used in water networks, electrical grids, and computer networks. They are also used in graph problems like the traveling salesperson problem, and they are used in important algorithms such as the min-cut max-flow algorithm.

There are many ways to find the minimum spanning trees, but Kruskal's algorithm is probably the fastest and easiest to do by hand.

1. Find the minimum spanning tree for the graph below. What is its total weight?

Example Graph

Show Answer

The minimum spanning tree is shown below. Its total weight is 31.

Minimum Spanning Tree

1. Eppstein, D. Spanning Trees. Retrieved April 10, 2016, from https://en.wikipedia.org/wiki/Spanning_tree
2. Benbennick, D. Wikipedia Complete Graph. Retrieved May 21, 2016, from https://en.wikipedia.org/wiki/Complete_graph
3. A, L. Wikipedia Connected Graph. Retrieved May 21, 2016, from https://en.wikipedia.org/wiki/Connectivity_(graph_theory)
4. A, L. Wikipedia Tree. Retrieved May 21, 2016, from https://en.wikipedia.org/wiki/Tree_(graph_theory)
5. A, K. Wikipedia Complete Bipartite Graph. Retrieved May 21, 2016, from https://en.wikipedia.org/wiki/Complete_bipartite_graph