World's most popular travel blog for travel bloggers.

# [Answers] Unclear about proof for unique MST given graph G with distinct weights

, ,
Problem Detail:

http://homepages.math.uic.edu/~leon/cs-mcs401-s08/handouts/mst.pdf I have some trouble understanding the proof above.

I understand that we assuming two MSTs, T and T', and an edge e that is the cheapest edge of G that located in T. Then the weight of this edge is larger than any weight on T', given that T' contains (x,y), by definition of MST.

My question is why do we assume that T' passes through (x,y)? Wouldn't it natural to assume that T' is completely disjoint from T?

#### Answered By : Yuval Filmus

The edge \$e\$ is not necessarily the cheapest edge of \$G\$ that is in \$T\$. Rather, it is the cheapest edge in the symmetric difference \$T \triangle T'\$. It could belong to either \$T\$ or \$T'\$ (but not both!), but since both cases are the same, we assume that it belongs to \$T\$ without loss of generality.

We don't need to separately consider the case that \$T\$ is disjoint from \$T'\$ and the case that they share some edges. All we need to know is that they are different and so their symmetric difference is not empty.