First thing to understand is that this topic will come under Graphs not trees.

Before solving questions related to Minimum Spanning Tree [MST], we shall take a look on what are MST?

In Minimum Spanning Tree, there is a sub part Spanning Tree.

## Spanning Tree Introduction:

Given a connected undirected graph, a spanning tree of that graph is a sub graph that has all the vertices and also a tree.

Means, a spanning tree should be connected [connected to all the vertices], acyclic [should not have any cycle] and should have all the vertices.

Below is a simple graph

Below are the different number of spanning tree for that graph.

Note:

If there are “n” vertices, then a spanning tree should have “n-1” edges. In the above image, we have 4 vertices, hence our spanning tree has “4 -1 = 3” edges.

## Then what is Minimum Spanning Tree?

Consider the below weighted graph:

Now you are a sales person, and let us consider each vertices as cities, and you need to visit all the places with minimum amount possible.

Below image is the solution for it.

## So where do we use MST?

We use MST in

- Network Design
- Maps
- Face Verification

In the next MST problems, we shall look at more complex problems with cycle and how to solve them using Prims and Kruskal’s algorithm.

### Further Reading: