A spanning tree of a connected graph G is a connected subgraph of G having no cycles. Every connected graph has a spanning tree. For example, the following graph has four distinct spanning trees.
Spanning Trees:
In general a graph will have very many spanning trees. Recall that the weight of a subgraph to be sum of all the edge weights in the subgraph. Different spanning trees have different weights, the minimum spanning tree is the spanning tree with the minimum weight.
Example: weights added to the graph above
