What is a spanning tree?

Spanning tree is an important field in both mathematics and computer science. Mathematically, we define a spanning tree T of an un-directed and connected graph G as a tree consisting of all the vertices and all or some edges of the graph G.

- Spanning tree is defined as a selection of some edges from G forming a tree such that every vertex is spanned by it. 

- This means that every vertex of graph G is present in the spanning tree but there are no loops or cycles. 

- Also, every bridge of the given graph must be present in its spanning tree. 

- We can even say that a maximal set of the graph G’s edges containing no cycle or a minimal set of the graph G’s vertices forms a spanning tree. 

- In the field of graph theory, it is common finding the MST or the minimum spanning tree for some weighted graph. 

- There are a number of other optimization problems that require using the minimum spanning trees and other types of spanning trees. 

The other types of spanning trees include the following:

Ø  Maximum spanning tree

Ø  An MST spanning at least k number of vertices.

Ø  An MST having at the most k number of edges per vertex i.e., the degree constrained spanning tree.

Ø  Spanning tree having the largest no. of leaves (this type of spanning tree bears a close relation with the “smallest connected dominating set”).

Ø  Spanning tree with the fewest number of leaves (this spanning tree bears a close relation with the “Hamiltonian path problem”).

Ø  Minimum diameter spanning tree.

Ø  Minimum dilation spanning tree.

- One characteristic property of the spanning trees is that they do not have any cycles. 

- This also means that if you add just an edge to the tree, a cycle will be created. 

- We call this cycle as the fundamental cycle. 

- For each edge in the spanning there exists a distinct fundamental cycle and therefore there arises a one – to – one correspondence among the edges that are not present and the fundamental cycles. 

- For a graph G that is connected and has V vertices, there are V-1 edges in its spanning tree. 

- Therefore, for a general graph composed of E edges, its spanning tree will have E-V+1 number of fundamental cycles.

- For the cycle space of a given spanning tree these fundamental cycles are used. 

- The notion of the fundamental cut set as well as of the fundamental cycle forms a dual.  

- If we delete even one edge from the spanning tree, two disjoint sets will be formed of the vertices. 

- The set of the edges that if taken out from the graph G partitioning the vertices in to same disjoint sets is defined as the fundamental cut set. 

- For a given graph G there are V-1 fundamental cut sets i.e., one corresponding to each spanning tree edge. 

- The fact that the edges of the cycles that do not appear in the spanning tree but only in the cut sets of the edges can be used to establish the relationship between the cycles and the cut sets.

What is Spanning Forest?

- The sub-graph generalizing the spanning tree concept is called the spanning forest. 

- A spanning forest can be defined as a sub-graph consisting in each of the connected component a spanning tree of the graph G or we can call it a maximal cycle free sub graph.

- For counting the number of spanning trees for a complete graph the formula used is known as the cayley’s formula.