A spanning tree in a connected graph is a subgraph consisting of all the vertices and some edges. So, a subgraph is a tree; it is a connected graph with no loops or cycles. Figure 5 shows an example of a spanning tree in a graph:

Figure 5. A spanning tree of a graph (shown in red)

A tree has minimum number of edges required to keep the vertices connected. Removing any edge from a tree will disconnect the graph. This can be useful in a map of roads that connect different places and has a minimal number of roads. With this motivation, we would really be interested in a spanning tree that has a minimum total length of roads. This may be important because constructing roads is a costly affair. Alternatively, we could design a bus route map for a city and have all the important places connected without creating too many routes; also, shorter routes are better. Such a spanning tree is called a minimum spanning tree. Finding a minimum spanning tree is an important...