What subset of edges in a connected, weighted graph connects all vertices with the minimum possible total edge weight?

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

Answer: (A)

The situation is about linking every vertex together with the smallest possible total edge weight. The structure that achieves this is the minimum spanning tree: a subset of edges that connects all vertices, contains no cycles, and has the minimal total weight among all such spanning trees. It uses exactly V−1 edges for a graph with V vertices, and it represents the cheapest way to build a network that reaches every node.

Why this fits best: it explicitly minimizes the overall cost of connecting all points, not just some pairwise distances. The idea is central to network design, where you want full connectivity without extraneous wiring.

Why not the others: a maximum spanning tree would try to maximize the total weight, which isn’t what’s being asked. A shortest path tree focuses on minimizing distances from a single root to every node, not on minimizing the sum of all edges in a network. A Steiner tree connects a specified subset of vertices and may include extra vertices to reduce cost, but when every vertex must be included, it effectively becomes the minimum spanning tree.