Designing Low-Cost Infrastructure With Spanning Trees

Infrastructure Networks as Weighted Graphs

Suppose a set of sites must be connected by cables, pipes or other links. Each possible link has a cost, and the aim is to connect every site while keeping the total cost as small as possible. A graph captures the choices: vertices represent sites, edges represent available links, and an edge’s weight records its cost.

In this model, assume each link’s cost is fixed and the total cost is the sum of the costs of the links chosen. We seek a network that connects all sites, but does not pay for a link that is unnecessary for connectivity. This is a minimum spanning tree problem. The model does not, by itself, account for capacity, reliability, backup routes or construction constraints; those may change which design is appropriate.

All graphs below are finite and simple, and their edges are undirected. For an infrastructure interpretation, assume the weights are costs, usually nonnegative. The algorithm and proof also work for real-valued weights. A connected graph has at least one spanning tree; if the available-link graph is disconnected, it is impossible to connect all sites using only those links. A tree is a connected graph with no cycle, so its links provide connectivity without a cycle of redundant links.

Kruskal’s Algorithm

Kruskal’s algorithm considers links in order of nondecreasing cost. It starts with no links selected. For each link in turn, it accepts the link if its endpoints are in different connected components of the links already selected; otherwise it rejects the link. In other words, accept a link exactly when adding it does not create a cycle. Stop when all vertices are connected. When costs tie, use any fixed order among tied edges.

The test for whether to accept an edge can be performed by checking whether its endpoints are already joined by a path of selected edges. If they are, adding it closes a cycle, so it is rejected. If they are not, it joins two components without creating a cycle. The selected edges therefore remain a forest throughout the process.

Why the Algorithm Is Correct

We prove that the algorithm produces a spanning tree of minimum cost. The proof uses an exchange argument: when the algorithm accepts a link, a minimum spanning tree can be adjusted to include it without increasing the total cost.

Proof. Let \(F\) be the set of edges accepted so far. We first show that at every stage, there is a minimum spanning tree containing \(F\). Initially \(F=\varnothing\), and a minimum spanning tree exists because the graph is finite and connected: it has at least one spanning tree, and there are only finitely many subgraphs to compare.

Suppose the algorithm accepts an edge \(e\), and assume there is a minimum spanning tree \(T\) containing all previously accepted edges. If \(e\in E(T)\), then \(T\) already contains the new set of accepted edges. Otherwise, adding \(e\) to \(T\) creates a cycle: the unique path in \(T\) between the endpoints of \(e\), together with \(e\), is a cycle. Let \(A\) and \(B\) be the two different components of the selected-edge forest just before \(e\) is accepted. The path in \(T\) between the endpoints of \(e\) must cross from \(A\) to \(B\). Choose an edge \(f\) on that path that crosses between these components.

The edge \(f\) is not among the previously accepted edges, since those edges lie within components of the forest. Also, \(f\) cannot have been processed before \(e\). If it had, its endpoints, which are in different components just before \(e\) is accepted, would also have been in different components when \(f\) was processed: components only merge as edges are accepted. The algorithm would then have accepted \(f\), a contradiction. Thus \(f\) is unprocessed, and the nondecreasing order gives \(w(f)\ge w(e)\).

Remove \(f\) from the cycle formed by adding \(e\) to \(T\), and call the resulting graph \(T'\). Removing an edge of that cycle keeps the graph connected, and the resulting graph has no cycle, so \(T'\) is a spanning tree. It contains the previously accepted edges and \(e\), and its cost is the cost of \(T\) plus \(w(e)-w(f)\), which is no greater than the cost of \(T\). Since \(T\) was already minimum-cost, \(T'\) is also a minimum spanning tree. This proves the claim at each accepted edge.

At the end, the selected edges connect all vertices. Indeed, if two or more components remained, connectedness of the original graph guarantees an edge between different components. When that edge was processed, its endpoints were also in different components, because components only merge; it would therefore have been accepted. This contradicts the claim that different components remain at the end. The selected edges form a connected forest, hence a spanning tree. By the claim, a minimum spanning tree contains all the selected edges; since both are spanning trees, they have the same number of edges, so they are equal. Therefore the algorithm’s output is minimum-cost. If the graph has one vertex and no edges, the algorithm returns the empty edge set, which is its spanning tree and is minimum-cost. \(\square\)

A finite tree on \(n\) vertices has \(n-1\) edges. For \(n\ge2\), a finite tree has a leaf: take a longest path, whose endpoint cannot have a neighbor outside the path (that would extend it) or another neighbor on the path (that would create a cycle). Removing the leaf and its single incident edge leaves a tree, so induction gives the edge count. For \(n=1\), the tree has zero edges, also \(n-1\). This gives a useful check on algorithm outputs.

Worked Networks

Interpreting the Design and Avoiding Pitfalls

In the first network, a tempting but incorrect calculation is to purchase every available link, adding \(2+3+4+6+7=22\). That connects the sites, but it is not a minimum-cost design: link \(LM\) closes a cycle and raises the cost from \(15\) to \(22\) without improving connectivity. The correction is to test each link against the edges already selected, not to include every proposed link.

Rejecting a link in an MST model does not mean that the link is useless in every engineering design. It means only that the link is unnecessary for connectivity in the least-cost spanning tree under the model’s assumptions. A real network might deliberately include extra links for backup routes, resilience or capacity. Those requirements are not represented by the minimum spanning tree objective alone.

For a computed result, check three things: every site is included, the chosen links connect the sites without a cycle, and the total is the sum of the selected costs. A connected acyclic graph on \(n\) vertices has \(n-1\) edges, which is a helpful structural check. To justify that the total is least, use the theorem’s exchange argument or a separate lower-bound argument, as in the five-site example; merely choosing some cheap links does not establish optimality.