2. Most classical minimum spanning tree algorithms use the notions of "safe" and "useless" edges described in lecture and Jeff Erickson's lecture notes, but there is an alternative formulation. Let G be a weighted undirected graph where the edge weights are distinct. We say that an edge e is dangerous if it is the longest edge in some cycle in G and useful if it does not lie in any cycle in G. (a) Prove that the minimum spanning tree of G contains every useful edge. [Hint: Spanning trees are connected subgraphs containing every vertex.] (b) Prove that the minimum spanning tree of G does not contain any dangerous edge. [Hint: Give an exchange argument. How can we decrease the weight of a spanning tree containing a dangerous edge?]