Which graph concept is the minimum total weight subset of edges that connects all vertices and contains no cycles?

Which graph concept is the minimum total weight subset of edges that connects all vertices and contains no cycles?

• A. Minimum Spanning Tree
• B. Maximum Spanning Tree
• C. Shortest Path Tree
• D. Steiner Tree

Answer: (A)

The minimum spanning tree is being described. It is the subgraph that connects every vertex with the smallest possible total edge weight while containing no cycles. In a connected graph, this means using exactly V−1 edges, ensuring full connectivity without any redundant links. This matches the requirement of connecting all vertices and staying cycle-free while minimizing the total weight. Other ideas don’t fit as well. A maximum spanning tree would do the opposite—maximize weight, not minimize. A shortest-path tree focuses on the shortest paths from one chosen root to all others and isn’t concerned with achieving the smallest total weight among all possible connected subgraphs. A Steiner tree seeks to connect a specified subset of vertices (possibly adding extra vertices), so it doesn’t necessarily connect every vertex in the graph with minimal total weight. So the described concept is the minimum spanning tree.

The minimum spanning tree is being described. It is the subgraph that connects every vertex with the smallest possible total edge weight while containing no cycles. In a connected graph, this means using exactly V−1 edges, ensuring full connectivity without any redundant links. This matches the requirement of connecting all vertices and staying cycle-free while minimizing the total weight.

Other ideas don’t fit as well. A maximum spanning tree would do the opposite—maximize weight, not minimize. A shortest-path tree focuses on the shortest paths from one chosen root to all others and isn’t concerned with achieving the smallest total weight among all possible connected subgraphs. A Steiner tree seeks to connect a specified subset of vertices (possibly adding extra vertices), so it doesn’t necessarily connect every vertex in the graph with minimal total weight.

So the described concept is the minimum spanning tree.