Search code examples
treegraph-theory

Uniquness of a graph. Why do we need to add e1 to B to create a cycle?

If each edge has a distinct weight then there will be only one, unique minimum spanning tree. This is true in many realistic situations, such as the telecommunications company example above, where it's unlikely any two paths have exactly the same cost. This generalizes to spanning forests as well.

Proof:

  1. Assume the contrary, that there are two different MSTs A and B.
  2. Since A and B differ despite containing the same nodes, there is at least one edge that belongs to one but not the other. Among such edges, let e1 be the one with least weight; this choice is unique because the edge weights are all distinct. Without loss of generality, assume e1 is in A.
  3. As B is an MST, {e1} ∪ B must contain a cycle C with e1.
  4. As a tree, A contains no cycles, therefore C must have an edge e2 that is not in A.
  5. Since e1 was chosen as the unique lowest-weight edge among those belonging to exactly one of A and B, the weight of e2 must be greater than the weight of e1.
  6. As e1 and e2 are part of cycle C, replacing e2 with e1 in B therefore yields a spanning tree with a smaller weight.
  7. This contradicts the assumption that B is an MST.

Question: Can't we just skip adding e1 to B and just get the smallest edge from B, and state that e1 < e2, since all edges are unique? Thus, it implies that there is only one MST possible.

Solution

  • No we can't.

    You can state that e1<e2, sure (that is already done in the actual proof). But that doesn't prove that B isn't also a MST. And therefore that there can't be two MST.

    See counter example (sort of)

    enter image description here

    With a spanning tree A in red

    And another one, with spanning tree B in blue

    enter image description here

    The fact that minimum edge of a, e1 (weight 1) is smaller that the one of B, e2 (weight 2), doesn't prove that A and B total weight are not equal (they are both equal to 11).

    Sure, you may say, A and B are not minimum spanning tree. Line S3-S0-S1-S2 has a total weight of 10, for example. But, well, sure, I can't exhibit a counter example with two minimum spanning tree, since it is true that minimum spanning tree are unique when all weight are distincts.

    So, my counter example isn't proving the falsehood that we could have 2 MST. But it proves that your proof of the contrary is invalid. Proving that e1<e2, doesn't prove that B total weight is different of A total weight. Because you are not using the fact that B is a minimum tree in the reasoning (if you were, of course, you could tell me that my counter-example doesn't invalidate your reasoning)

    On the other hand, if I were trying to use the correct reasoning with my counter example: if you add e1 (edge whose weight is 1. Since all have different weight, we can use unambiguously their weight as their name), to B, to form a subgraph {e1}∪B = {e1, e2, e3, e6}, then there is a cycle (all nodes were connected before we add e1, since B is a spanning tree. Including S0 and S1: there was already a path in B from S0 and S1. That has now another path. So we can go from S0 to S1 through B1, and back from S1 to S0 via e1; that's a cycle).

    So we can remove an edge from this cycle. One that is not in A (e2). So, we remain with a tree made of e1, e3, e6. And that new tree has a total weight smaller than the one of B (10). (So far, I said nothing wrong).

    And there, we have the contradiction. B couldn't be a MST, since we know a smaller one (e1,e3,e6). In my example, it just shows that, indeed A and B are not minimum. But if you start with A and B being mininum, you reach a contradiction.

    Algorithm to build smaller tree

    What the proof use here is an algorithm that is able to build a smaller tree from two different but same weight trees.

    If you can give 2 different spanning trees trees of the same total weight, then, we can build a smaller spanning tree using those steps.

    • Consider all edge that exist in one tree but not the other. Let's call e1 the smaller edge of those, and A the tree that e1 belongs to. And B the other tree (that have no edge e1).
    • Consider subgraph {e1}∪B. It has a cycle. Because there is a path through B that connect the two nodes x and y of e1. A path that do not use e1, since e1 is not in B. So you have a cycle x--(B)-->y--(e1)-->x.
    • In that cycle there has to be one edge, let's call it e2 that is not in A. Because if there wasn't such a e2, then that would mean that all edges of that cycle are in A. Therefore that there is a cycle in A. And there aren't any cycle in trees, and A is a tree. So e2, a edge that in the previously mentioned cycle but not in A, exists.
    • If we remove it, from {e1}∪B, and therefore consider tree {e1}∪B{e2} we again have a tree (the cycle has been broken).
      • That tree is a spanning tree. We can connect all edge to any other (it is B. But for e2. But any path that, in B, use e2, could now go through e1 and the remaining of the broken cycle).
      • And we know that the total weight of that new spanning tree is the total weight of B + the weight of e1, minus the weight of e2. Since weight of e2 is bigger than weight of e1, that means that the total weight of that new tree is smaller than the one of B.

    So, that algorithm builds, given 2 different spanning trees of same total weight W, build a new spanning tree whose total weight is strictly smaller than W.

    It is not a very useful algorithm to build a minimal spanning tree (not that easy to find 2 same weight spanning tree). But it is useful to prove that minimal spanning tree is unique. If it weren't unique, then it wouldn't be minimal. Since if if weren't unique, then you could build a smaller one with that algorithm.