The following statements may or may not be correct. In each case, either prove it (if it is correct) or give a counterexample (if it isn’t correct). Always assume that the graph G = (V, E) is undirected and connected. Do not assume that edge weights are distinct unless this is specifically stated.
(a) If graph G has more than |V| − 1 edges, and there is a unique heaviest edge, then this edge cannot be part of a minimum spanning tree.
(b) If G has a cycle with a unique heaviest edge e, then e cannot be part of any MST.
(c) Let e be any edge of minimum weight in G. Then e must be part of some MST.
(d) If the lightest edge in a graph is unique, then it must be part of every MST.
(e) If e is part of some MST of G, then it must be a lightest edge across some cut of G.
(f) If G has a cycle with a unique lightest edge e, then e must be part of every MST.
(g) The shortest-path tree computed by Dijkstra’s algorithm is necessarily an MST.
(h) The shortest path between two nodes is necessarily part of some MST.
(i) Prim’s algorithm works correctly when there are negative edges.
(j) (For any r > 0, define an r-path to be a path whose edges all have weight < r.) If G contains an r-path from node s to t, then every MST of G must also contain an r-path from node s to node t.
We need at least 10 more requests to produce the solution.
0 / 10 have requested this problem solution
The more requests, the faster the answer.