iv Spanning Trees and Optimization Problems (Excerpt)

What is a minimum spanning tree for the weighted graph in Figure 2.1? Notice that a minimum spanning tree is not necessarily unique. FIGURE 2.1: A weighted graph. Figure 2.2 gives four minimum spanning trees, where each of them is of total weight 14. Let G + e denote the graph obtained by inserting edge e into G. LEMMA 2.1 Any two vertices in a tree are connected by a unique path. LEMMA 2.2 Let T be a spanning tree of a graph G, and let e be an edge of G not in T. Then T + e contains a unique cycle. THEOREM 2.1 Let F1, F2,..., Fk be a spanning forest of G, and let (u, v) be the smallest of all edges with only one endpoint u ∈ V (F1). Then there is an optimal one containing (u, v) among all spanning trees containing all edges in ∪ k i=1 E(Fi). ii