Which of the following is NOT a characteristic of a

Solution

A minimum spanning tree (MST) is not necessarily unique. While there is only one MST with the minimum total weight for certain graphs, when there are multiple edges with the same weight, there can be more than one valid MST. In such cases, different spanning trees with the same weight may be possible. For example, in a graph with parallel edges of equal weight, there can be multiple ways to select edges while still maintaining the minimum total weight. The characteristics of an MST ensure that it has the least total weight, contains exactly V−1V-1 V − 1 edges, and connects all vertices without forming cycles. However, its uniqueness can be compromised in cases of weight ties. Therefore, it’s incorrect to assume that an MST is always unique. Why Other Options Are Incorrect:

• A) This is correct for MSTs. An MST contains the edges that minimize the total weight of all edges while still maintaining connectivity between all vertices.
• B) This is correct. An MST in a connected, undirected graph will always have exactly V−1V-1 V − 1 edges, where VV V is the number of vertices.
• D) This is incorrect. By definition, a spanning tree is acyclic. A minimum spanning tree cannot contain cycles, as it would violate the tree property.
• E) This is correct. An MST connects all vertices of the graph and ensures there are no disjoint components, ensuring full connectivity.