# Spanning tree

A spanning tree is a sub-graph of an undirected connected graph, which includes all the vertices of the graph with a minimum possible number of edges. If a vertex is missed, then it is not a spanning tree.

The edges may or may not have weights assigned to them.

The total number of spanning trees with n vertices that can be created from a complete graph is equal to n(n-2).

If we have n = 4, the maximum number of possible spanning trees is equal to 44-2 = 16. Thus, 16 spanning trees can be formed from a complete graph with 4 vertices.

# Minimum Spanning tree

A minimum spanning tree is a spanning tree in which the sum of the weight of the edges is as minimum as possible.

The minimum spanning tree from a graph is found using the following algorithms:

-Prim's Algorithm
-Kruskal's Algorithm