We consider minimum-cost spanning trees, both in lattice and Euclidean
models, in d dimensions. For the cost of the optimum tree in a box of size L,
we show that there is a correction of order L^theta, where theta < 0 is a
universal d-dependent exponent. There is a similar form for the change in
optimum cost under a change in boundary condition. At non-zero temperature T,
there is a crossover length xi approx equal to T^{-nu}, such that on length
scales larger than xi, the behavior becomes that of uniform spanning trees.
There is a scaling relation theta=-1/nu, and we provide several arguments that
show that nu and -1/theta both equal nu_perc, the correlation length exponent
for ordinary percolation in the same dimension d, in all dimensions d > 1. The
arguments all rely on the close relation of Kruskal's greedy algorithm for the
minimum spanning tree, percolation, and (for some arguments) random resistor
networks. The scaling of the entropy and free energy at small non-zero T, and
hence of the number of near-optimal solutions, is also discussed. We suggest
that the Steiner tree problem is in the same universality class as the minimum
spanning tree in all dimensions, as is the traveling salesman problem in two
dimensions. Hence all will have the same value of theta=-3/4 in two dimensions.