Weighted Graphs And The Minimum Spanning Tree Objective

From a Connected Graph to a Weighted Objective

A spanning tree connects every vertex of a graph without using any cycle. When edges also have costs, lengths, or other numerical weights, different spanning trees can have different total weights. The minimum spanning tree problem is to choose a spanning tree with the smallest possible total weight. This is an optimization objective: finding any spanning tree is not enough unless its weight is minimum.

Weights may represent costs, distances, or another quantity to be minimized. We allow negative weights as well as zero and positive weights. The definition of a weighted graph does not require weights to be distinct.

A spanning tree must include every vertex, including any vertex that has no incident edge in a proposed edge set. It uses only edges of \(G\), and it must be both connected and acyclic. Thus the optimization takes place over the spanning trees of the underlying graph; weights rank those feasible choices but do not change which edge sets are trees.

Why the Objective Is Well Defined

For a nonempty connected graph, there is at least one spanning tree. Also, because the graph is finite, it has only finitely many edge subsets. These facts together ensure that an MST exists, even when some weights are negative or several spanning trees have the same weight.

Proof. First we show there is a spanning tree. Among the connected spanning subgraphs of \(G\), choose one with as few edges as possible; such a choice exists because there are finitely many edge subsets and \(G\) itself is a connected spanning subgraph. If the chosen subgraph contained a cycle, deleting any edge of that cycle would leave it connected: the other edges of the cycle still give a route between the endpoints of the deleted edge. This would produce a connected spanning subgraph with fewer edges, contradicting minimality. Therefore the chosen subgraph is connected and acyclic, so it is a spanning tree. There are finitely many spanning trees, since each is an edge subset of the finite set \(E(G)\), and there is at least one. Their total weights form a nonempty finite set of real numbers, which has a least member. A spanning tree with that weight is an MST. \(\square\)

The nonempty and connected conditions matter. A disconnected graph has no connected spanning subgraph, hence no spanning tree. For a graph with one vertex and no edges, the one-vertex graph is a tree: its edge set is empty and its weight is \(0\). We use the usual convention here that a connected graph is nonempty and every pair of its vertices can be joined by a path.

Proof. We use induction on \(n\). If \(n=1\), a tree has no edges, so it has \(0=n-1\) edges. Now let \(n\geq2\), and assume the result for trees on \(n-1\) vertices. A longest path in the tree exists because the tree is finite. An endpoint of that path has degree \(1\): it has its neighbor on the path, and any other neighbor outside the path would extend the path, while any other neighbor on the path would create a cycle. Remove that endpoint and its single incident edge. The remaining graph is acyclic, and it is connected because paths between its remaining vertices cannot need a degree-one vertex as an intermediate vertex. It is therefore a tree on \(n-1\) vertices, with \(n-2\) edges by induction. Restoring the removed edge gives \(n-1\) edges in the original tree. \(\square\)

Consequently, when \(G\) has \(n\geq1\) vertices, every spanning tree uses exactly \(n-1\) edges. This is a feasibility check, not an optimization criterion: having \(n-1\) edges alone does not guarantee that an edge set is connected and acyclic.

Comparing Spanning Trees by Weight

This example separates two questions. The edge set \(\{ab,bc\}\) is a spanning tree, but it is not minimum. A solution to the minimum spanning tree objective must satisfy the spanning-tree conditions and achieve the least weight among all such choices.

Negative Weights and Ties

The objective is the sum of the chosen edge weights, not a requirement that every chosen edge have positive weight. A negative edge can belong to an MST. Likewise, if different spanning trees attain the same least total, each is an MST; the definition does not require uniqueness.

A Common Edge-Count Pitfall

A frequent mistake is to treat any connected edge set as a spanning tree, or to think that adding more edges always improves a tree. Extra edges can create a cycle, and a spanning tree on \(n\) vertices has exactly \(n-1\) edges. For instance, in the four-vertex graph of the second example, no four-edge subset is a spanning tree because a tree on four vertices has three edges.

In that same graph, every four-edge subset contains a cycle. If \(ac\) is omitted, the remaining edges form the four-cycle \(ab,bc,cd,da\). If any other edge is omitted, the remaining graph still contains a triangle: omitting \(ab\) or \(bc\) leaves \(acd\), while omitting \(cd\) or \(da\) leaves \(abc\). This illustrates why counting edges is a useful check but does not replace checking connectedness and acyclicity.

There is also a separate optimization pitfall: a spanning tree that is easy to identify need not have minimum weight. The definition requires comparison with every feasible spanning tree, whether by exhaustive enumeration on a small graph or by a justified algorithm. The algorithms and their correctness arguments are developed after the objective itself is established.

Summary of the Objective

For a finite, nonempty, connected weighted graph, the feasible objects are its spanning trees, each containing all vertices and exactly \(n-1\) edges. The weight of a candidate is the sum of its edge weights. An MST is any feasible candidate whose total is no greater than that of every other candidate. The weights may be negative, and the minimum may be attained by more than one tree.