= Solution
Assume the graph is connected so that a <minimum spanning tree> exists, and let $T$ be the output of <Kruskal's algorithm>. With distinct weights there is a strict total <edge> ordering. Suppose another <minimum spanning tree> $T'\ne T$ existed. Choose $e\in T\setminus T'$ and increase only $w(e)$ by a positive $\varepsilon$ so small that the strict ordering of \i[all] <edge> weights remains unchanged. For a finite graph such an $\varepsilon$ exists, using less than the gap to the next larger weight; if $e$ is largest, any sufficiently small positive increase works.
Running <Kruskal's algorithm> again examines exactly the same order and makes exactly the same component decisions. It therefore still returns $T$, which must remain optimal for the perturbed weights. But $T$ has become more expensive by $\varepsilon$, while $T'$ is unchanged. They had equal original weight, so now $T'$ is cheaper, a contradiction. This proves that <distinct weights imply a unique minimum spanning tree>.
The converse is \b[false]. A triangle with <edge> weights $1,1,2$ has a unique <minimum spanning tree>, consisting of its two weight-one <edges>. Its total is $2$, while either other spanning tree has total $3$. Thus equal <edge> weights permit, but do not force, multiple optimum trees. The same perturbation proof applies componentwise to a <minimum spanning forest>.
Back to article page
