Assume that the weights in a graph are positive. Prove that you can rescale them by adding a constant to all of them or by multiplying them all by a constant without affecting the MSTs, provided only that the rescaled weights are positive.
Show that, if edge weights are positive, a set of edges that connects all the vertices whose weights sum to a quantity no larger than the sum of the weights of any other set of edges that connects all the vertices is an MST.
Show that the property stated in Exercise 20.2 holds for graphs with negative weights, provided that there are no cycles whose edges all have nonpositive weights.
20.4 How would you find a maximum spanning tree of a weighted graph?
20.5 Show that if a graph's edges all have distinct weights, the MST is unique.
20.6 Consider the assertion that a graph has a unique MST only if its edge weights are distinct. Give a proof or a counterexample.
• 20.7 Assume that a graph has t < V edges with equal weights and that all other weights are distinct. Give upper and lower bounds on the number of different MSTs that the graph might have.