Mathematics — Graph Theory · minimum-spanning-tree
Problem
Let G=(V,E,φ) be a connected multigraph. Let w:E→R be a map that assigns a real number w(e) to each edge e. We shall call this real number w(e) the weight of the edge e.
If H=(W,F,φ∣F) is a subgraph of G, then the weight w(H) of H is defined to be ∑f∈Fw(f) (that is, the sum of the weights of all edges of H).
A w-minimum spanning tree of G means a spanning tree of G that has the smallest weight among all spanning trees of G.
In our first proof of Theorem 5.4.6, we have seen a way to construct a spanning tree of G by successively removing non-bridges until only bridges remain. (A non-bridge means an edge that is not a bridge.)
Now, let us perform this algorithm, but taking care to choose a non-bridge of largest weight (among all non-bridges) at each step. Prove that the result will be a w-minimum spanning tree.