Let G = (V, E) be an undirected, fully-connected graph with real weights that are all distinct (i.e., no two edges have the same weight). Let T' be the minimum spanning tree of G and let T'' be a secondbest spanning tree (i.e., it has the minimum weight among all spanning trees of G, excluding T' . For all the questions below, assume that G is not a tree (i.e., it has additional edges and thus contains at least one cycle). (a) Show that the minimum spanning tree is unique.

(b) Show that T'' is not necessarily unique. Hint: Come up with a simple counter-example.

(c) Prove that G contains edges (u, v) T' and (x, y) 6 T' , such that T{(u, v)}{(x, y)} is a second-best minimum spanning tree of G.

(d) Prove that if you replace two or more edges of T' , you cannot form a second-best minimum spanning tree.