You must wire up every town with the least total cable. The answer is a minimum spanning tree: connect all nodes with no cycles, at the lowest total edge weight. Kruskal’s method is beautifully simple — sort the edges cheap-to-dear and add each one UNLESS it would form a loop. Greedy, and provably minimal. Slide to build the tree edge by edge.
A minimum spanning tree connects all V nodes of a weighted graph with V−1 edges of minimum total weight and no cycles. Kruskal’s algorithm sorts edges by weight and adds each if its endpoints are in different components (using a union-find/disjoint-set structure to detect cycles), stopping at V−1 edges. The greedy choice is optimal by the CUT PROPERTY: the lightest edge crossing any cut is in some MST. Runs in O(E log E). It designs least-cost networks and clustering. A fail-loud self-check throws unless the MST has V−1 edges and the known minimum weight. ◆ real graph algorithm, node-verified.
Kruskal gives one MST (ties can yield several of equal weight); the V−1 edges, acyclicity, and minimum total weight are exact. Union-find makes cycle checks near-constant time.