3
$\begingroup$

I am trying to prove the following property on graphs:

Let $G$ be a graph with a weight assigned to each edge and suppose that there are no two different edges with equal weight. Show that there is a unique minimum spanning tree of $G$

This is what I've tried so far:

Suppose there are at least two distinct minimum spanning trees $A_1$ and $A_2$ of $G$. Then there exists $e_2 \in \text{edges}(A_2 \setminus A_1)$. Then the graph $T = A_1 + e_2$ has a unique cycle $C$ that contains $e_2$. If there is an edge $e \in C$ with weight greater than the weight of $e_2$, then $T' = T - e$ is a tree with total weight less than $A_1$, which is absurd by definition of minimum spanning tree. Now, suppose $e_2$ is the edge with maximum weight on this cycle, take $e' \in C$ such that $e' \not \in A_2$ (note that there must be such an edge since otherwise $A_2$ would contain the cycle $C$). Then $\text{weight}(e') < \text{weight}(e_2)$ (here I am using the hypothesis that all edges of $G$ have different weights) and if we define the graph $T'' = (A_2 - e_2) + e'$, then $T''$ is a spanning tree with total weight less than the total weight of $A_2$, which is absurd since $A_2$ was a minimum spanning tree of $G$.

I would like to know if this solution is correct, any suggestions to improve or generate an alternative solution are welcomed. Thanks in advance.

$\endgroup$
  • 3
    $\begingroup$ Imagine constructing the spanning tree step by step using either Prim's or Kruskal's algorithm. At each step, when all edges have different weight, the argument for the algorithm's correctness actually gives you that the edge you select must be in every minimal spanning tree that contains the edges already selected. By induction, when you're done you know that every minimal spanning tree contains all of the edges you've selected (and it certainly can't contain more than those). $\endgroup$ – Henning Makholm Jul 7 '18 at 18:56
  • 1
    $\begingroup$ A possible problem with your proof is this: how do you know that $A_2+e'$ will contain a cycle which has $e_2$ as an edge? For all I know, $T''$ may end up being a disconnected subgraph with a cycle. $\endgroup$ – Batominovski Jul 7 '18 at 18:59
1
$\begingroup$

If you set $e_2$ to be the (unique) edge with minimum weight in $E(A_1 \setminus A_2)$ $\cup E(A_2 \setminus A_1)$ [and then assume WLOG that $e_2 \in A_2)$], the existence of such an $e'$ in the cycle in $A_1 + \{e_2\}$ would itself be a contradiction. And so the uniqueness of the Minimum-Weight Spanning Tree would follow.

What @Batominovski said in his comment.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.