a minimum spanning tree
Imagine you must connect a set of towns with cables so that electricity can flow between any two of them, and you want to spend as little total cable as possible. You do not need a cable between every pair — you just need the whole network to hang together as one connected piece. The cheapest such set of cables is a minimum spanning tree: connect everything, for the least total cost, with no wasteful extra links.
Formally, given a connected, undirected graph with a weight on each edge, a spanning tree is a subset of edges that connects all V vertices and contains no cycle (so it has exactly V-1 edges). A minimum spanning tree is a spanning tree whose total edge weight is the smallest possible. Why exactly V-1 edges? Fewer would leave the graph disconnected; more would necessarily create a cycle, and a cycle contains a removable edge that keeps everything connected while lowering cost — so a minimum solution never has a cycle. Two facts drive every MST algorithm: the cut property (the cheapest edge crossing any split between vertices is safe to include) and the cycle property (the most expensive edge on any cycle is safe to exclude).
MSTs are the backbone of network design — laying fiber, water pipes, or circuit traces at minimum cost — and they appear inside clustering algorithms and approximation schemes for hard problems like the traveling salesman. Two algorithms find one efficiently: Kruskal's (add cheapest edges that do not form a cycle, using union-find) and Prim's (grow one tree outward, always adding its cheapest exiting edge). A clarification worth keeping: the MST minimizes TOTAL edge weight for connecting everything; it is NOT a shortest-path tree, which minimizes distance from a single source — the path between two vertices within an MST is often not their shortest path. Also, the MST is unique only when all edge weights are distinct.
Four towns with edges A-B (1), B-C (2), A-C (3), C-D (4), B-D (5). An MST picks A-B (1), B-C (2), C-D (4), total 7. It skips A-C (3) because A and C are already connected through B, and skips B-D (5) because C-D is the cheaper way to reach D. Three edges (V-1 = 3) connect all four towns at minimum cost.
An MST uses exactly V-1 edges to connect everything; any extra edge would form a cycle and could be dropped to save cost.
An MST is not a shortest-path tree. It minimizes total edge weight with no source in mind, so the route between two vertices inside the MST may be far longer than their actual shortest path.