Finding the minimum spanning tree

With the properties we just discussed, we can now define an algorithm for finding the minimum spanning tree of a graph. Suppose a set of edges F is already given and they are members of the minimum spanning tree G. Now we are trying to find another edge that is also a member of the minimum spanning tree. First, we choose an edge e whose cost is minimum when compared to the rest of the edges, E and F in this case. Since some of the edges are already given, some of the vertices are already connected. If the chosen edge e is between two vertices that are already connected, we simply reject this edge and find the next edge with minimum cost. We do this until we find an edge f between two vertices that are not already connected. Our claim is that f is a new member of the minimum spanning tree. To confirm this, let's assume that f is between the vertices A and B. From the description of our procedure, A and B are not connected. Let's make two partitions of the...