From: "Alexander Boogert" <a.f.boogert@student.utwente.nl>
Subject: Re: HELP!!! (Graph theory)
Date: Thu, 11 Feb 1999 23:26:00 +0100
Newsgroups: sci.math
Keywords: constructing minimum spanning trees

Rob Beattie wrote in message
<36C32BBB.DC4E9162@r-beattie.freeserve.co.uk>...
>Suppose T is a minimum spanning tree in the weighted graph G.  Show that if
>all the weights assigned to the edges of G are distinct then G has a
>unique minimum spanning tree.
>

The general idea of constructing a mst is this (and simultaniously the
proof)

Say you have a part S of G in which you know you have a mst. Then there are
connections between S and S* = G \ S as you have a graph. Take the
connection (say to point h in S*) with the least value (they are all
distinct so you can do this) and widen S to {S,h}. Then {S,h} is still a
mst.

So: if one begins with one point in G I have a mst and one can widen it in
the above way until S = G. Then S is the mst of G!

Alexander