New 55% Off on All Courses - Enroll Now! Click Here

    Question

    Which of the following is NOT a characteristic of a

    minimum spanning tree (MST) in a connected, undirected graph?
    A It contains the minimum total weight of all edges Correct Answer Incorrect Answer
    B It has exactly V−1 edges, where V is the number of vertices Correct Answer Incorrect Answer
    C It is unique and only one minimum spanning tree can exist for a graph Correct Answer Incorrect Answer
    D It may contain cycles in its structure Correct Answer Incorrect Answer
    E All vertices are connected without any disjoint components Correct Answer Incorrect Answer

    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.

    Practice Next