Spanning Trees:
A spanning tree of a connected, undirected graph is a subgraph that includes all the vertices of the original graph and forms a tree without forming any cycles.
• In other words, a spanning tree is a tree that spans all the vertices of a graph, connecting them together without creating loops or circuits.
• A graph may have more than one spanning tree.
Note: A Spanning tree does not exist for a disconnected graph.
• A subgraph T of a connected graph G is called spanning tree of G if T is a tree and T include all vertices of G.

‣ The number of spanning trees in a complete graph with N vertices isNN-2
For example: N=4, then maximum number of spanning tree possible =44-2= 16
Applications of A Spanning Tree:
Spanning trees find applications in various fields due to their ability to ensure connectivity, simplify graph structures, and optimize resource usage.
Here are some specific applications of spanning trees:
- Network Design
- Circuit Design
- Telecommunication
- Transportation Planning
- Power Distribution Networks
Minimum Spanning Tree:
A minimum spanning tree (MST) of a connected, undirected graph is a subset of the edges of the graph that connects all the vertices of the graph with the minimum total weight.
• The total edge weight is the sum of the weights of all the edges in the spanning tree. Finding the minimum spanning tree is a common problem in graph theory and optimization.
Algorithms to Find Minimum Spanning Tree of a Graph:
There are several algorithms to find the minimum spanning tree (MST) of a graph. The two primary algorithms are Kruskal’s Algorithm and Prim’s Algorithm.
Some of them are listed below:
- Kruskal’s Algorithm
- Prim’s Algorithm
- Boruvka’s Algorithm
- Reverse-Delete Algorithm
‣ Kruskal’s Algorithm:
Kruskal’s Algorithm is a greedy algorithm used to find a minimum spanning tree in a connected, undirected graph.
• The algorithm operates by repeatedly adding the smallest edge that does not form a cycle with the edges already chosen.
‣ Prim’s Algorithm:
Prim’s Algorithm is a greedy algorithm used for finding a minimum spanning tree (MST) in a connected, undirected graph.
• Similar to Kruskal’s Algorithm, Prim’s Algorithm builds the minimum spanning tree step by step, always selecting the edge with the minimum weight.