[Math] Proof of if each edge in a graph has a distinct weight, then there will be only one unique MST.

discrete mathematicsgraph theory

So I'm trying to go over the proof of why there can only be one unique MST if all edges in the graph has a distinct weight.

So the proof I'm trying to understand is:

  1. Assume that there are two MSTs A, B for graph G.
  2. There must be at least one edge that is in A but not B or B but not A.
  3. Let e1 be the edge with least weight among all such edges, and suppose e1 belongs to A but not B.
  4. As B is an MST, B union {e1} should create a cycle, C
  5. As a tree, A contains no cycles, therefore C must have an edge e2 that is not in A
  6. Since e1 was chosen as the unique lowest weight edge among those belonging to exactly one of A and B, w(e2) > w(e1).
  7. Replacing e2 with e1 in B therefore yields a spanning tree with smaller weight.
  8. This contradicts the assumption that B is an MST.

I don't understand parts 5 and 6, why does A not having a cycle lead to C having an edge not in A?
And why does e2 weigh more than e1, could there not be an edge in B that weighs less than e1? Since e1 is the lowest weight edge from A, NOT B, hence there could be an edge in the cycle created by (B union e1) that weighs less than e1 because that edge could be an edge in B but not in A with minimum weight.

I apologize if I made the wording too complicated, but I really want to understand this proof.

Thanks

Best Answer

  1. $C$ is a cycle; if all of $C$'s edges were in $A$, then $A$ would have a cycle and not be a tree. So there has to be some edge of $C$ not in $A$.

  2. Your definition in step 2 doesn't match - you claim that $e_1$ is chosen as the unique lowest weight edge belonging to exactly one of either $A$ or $B$ in step 6. Under this assumption, then the claim is correct. We should modify step 2 to be "There must be at least one edge that is in $A$ but not $B$ or $B$ but not $A$." Then step 3 becomes "Let $e_1$ be the edge with least weight among all such edges, and suppose $e_1$ belongs to $A$ but not $B$." Then the other case follows symmetrically.

Related Question