gen-briefly-explain-a-minimum-spanning-tree-and-one-common-misco-8431

Briefly explain a minimum spanning tree and one common misconception about it.

# Minimum Spanning Tree (MST) A **minimum spanning tree** is a subset of edges in a weighted, connected graph that: - Connects all vertices together - Contains no cycles (forms a tree) - Has the minimum possible total edge weight For a graph with *n* vertices, an MST contains exactly *n-1* edges. ## Common Misconception **"An MST must contain the shortest path between every pair of vertices."** This is **false**. An MST minimizes the *total* weight of all edges, not individual paths. The path between two vertices in an MST may be longer than the shortest path in the original graph. **Example:** Consider three vertices A, B, C where: - A-B: weight 1 - B-C: weight 1 - A-C: weight 3 The MST uses edges A-B and B-C (total: 2). The path from A to C in the MST has length 2, but the direct edge A-C in the original graph would be a shorter path (length 3... wait, that's longer). Better example: If A-C had weight 1.5, the MST would still use A-B-C (total tree weight: 2), making the A-to-C path in the MST cost 2, even though a direct path of 1.5 exists.