The Problem: Indicate whether the following statements are true or false:
- a. If e is a minimum-weight edge in a connected weighted graph, it must be among edges of at least one minimum spanning tree of the graph.
- b. If e is a minimum-weight edge in a connected weighted graph, it must be among edges of each minimum spanning tree of the graph
- c. If edge weights of a connected weighted graph are all distinct, the graph must have exactly one minimum spanning tree
- d. If edge weights of a connected weighted graph are not all distinct, the graph must have more than one minimum spanning tree
From those two statements, I concluded that the first two statements(a, b) are true while the last two statements(c,d) are false.
Here is the diagram I used to illustrate that the last option, d, is false.
The edge weights are not distinct(two twos) and there is only one minimum spanning tree.
Can anyone give a counterexample graph to choice option c? I tried some examples(too many to include in here) but each time with distinct weights, using Prim's algorithm, I only found one MST.