In this section we define the minimum-cost spanning tree problem and a related path-finding problem. We give a recurrence for solving the path-finding problem via dynamic programming. We then prove that the solution to the path-finding problem contains the solution to the minimum-cost spanning tree problem.
Given an n-node connected
undirected graph 
,
where V is the set 
, and where each edge 
in E has cost 
, the minimum-cost spanning tree
problem is to find a subgraph that connects the vertices in V such
that the sum of the costs of the edges in the subgraph is minimum. We
assume that the edge costs are unique. (If not, lexicographical
information can be added to make them unique.) For convenience, we
also assume that if 
is not in E then it has cost 
.
The path-finding problem is to compute the cost 
for each 
of the shortest (lowest-cost) path from i to j that
passes through vertices only in the set 
, where
the cost of a path is defined to be the highest cost of any edge
on the path. For any i and j, the shortest path from i to j
with no intermediate vertex higher than k either passes through k
or does not. In the first case, the cost of the shortest path from
i to j is either the cost of the shortest path from i to k or
the cost of the shortest path from k to j, whichever is higher.
In the second case, we have 
. Thus,
can be computed by the recurrence
The following theorem shows that the unique minimum-cost spanning tree can be recovered from the costs of the shortest paths.
Proof:
The proof has two parts. We first show that if 
is a tree
edge then 
. We then show that if 
then the edge 
is in the tree. First, assume that
is a tree edge, but that 
.
Consider the cut of the graph that 
crosses, but no other
tree edge crosses. Since 
, there must be
some path from i to j whose highest-cost edge has cost 
. Hence, every edge on this path has cost less than
. This path must cross the cut at least once. Replacing
the edge 
by any edge on the path that crosses the cut
reduces the cost of the tree, a contradiction. Conversely, assume
that 
, but that 
is not a tree edge.
Adding the edge 
to the tree forms a cycle whose highest-cost
edge costs more than than 
. Replacing this edge by
yields a tree with smaller cost, a contradiction. width 4pt height 8pt depth 1.5pt