How many minimal spanning trees are there when all edge costs are distinct?

Suppose all costs on edges are distinct. How many minimal spanning trees are possible?

I dont know if this question is supposed to be easy or hard, but all I can come up with is one, because Kruskal's, and any other greedy algorithm should choose all the smallest weighted edges first. Then, if all weights on all edges are distinct, then there are no two equivalently weighted minimum spanning trees if a greedy algorithm is used.

• Just one. – Me. Mar 24 '13 at 14:56

Consider Kruskal's or Prim's algorithms to get minimal spanning trees. They consider arcs in increasing order of cost. If all costs are different, the order in which they are added is fixed, and so is the spanning tree constructed. It is unique in this case.

• That only shows Kruskal and Prim will return a unique tree? – Hendrik Jan Mar 24 '13 at 15:56
• Kruskal and Prim return a minimal spanning tree, if you look at the proof they do so, taking out an edge and putting in another maintaining the spanning tree gives a tree with a larger value, unless the edges switched have the same weight. Thus the tree constructed in this case is the minimal spanning tree. – vonbrand Mar 24 '13 at 16:24
• @vonbrand, one lacks a proof that it isn't possible to swap two set of edges of the same weight while maintaining the tree property. – AProgrammer Mar 25 '13 at 10:31
• @AProgrammer. Kruskal and Prim give a MST. Part of their correctness proof is that if in a step they leave out the next possible minimal cost edge, the resulting tree isn't minimal cost. See also Raphael's answer. – vonbrand Mar 25 '13 at 13:24
• So we need to look into one of the algorithm correctness proofs to extract what we need; that makes your answer a bit too short, especially since a direct proof is readily available. – Raphael Mar 26 '13 at 13:45

Assume there were at least two distinct minimal spanning trees. What can you deduce?

Consider an edge $e_1$ in one tree and the cut it induces. What can you say about the edges that are both in this cut and in the other tree?

The ultimate hint:

With this knowledge, can you construct a smaller MST?

This is the standard argument when working spanning trees (and several other graph problems).

You can give an explicit condition for whether an edge should be in the MST. Consider edge between x and y with weight w. Remove all edges with weights greater than or equal to w. Are x and y still connected? If so, edge e should not be in the MST, otherwise it should.

This isn't qualitatively different to previous answers. It makes sense to prove it using Kruskal's algorithm, but perhaps is an easier statement to think about in the context of uniqueness. More details at: http://tinyurl.com/d9lnb82.