$\begingroup$

Show that there's a unique minimum spanning tree (MST) in case the edges' weights are pairwise different $(w(e)\neq w(f) \text{ for } e\neq f)$.

I thought that the proof can be done for example by contradiction, saying that we have $2$ different MST meaning that somewhere was possible to pick from more edges, so $w(e) = w(f)$ for $e\neq f$, contradiction. Apparently this is not correct.

How would you show that a graph has a unique MST if all edges have distinct weights?

$\endgroup$ 0

5 Answers

$\begingroup$

If $T_1$ and $T_2$ are distinct minimum spanning trees, then consider the edge of minimum weight among all the edges that are contained in exactly one of $T_1$ or $T_2$. Without loss of generality, this edge appears only in $T_1$, and we can call it $e_1$.

Then $T_2 \cup \{ e_1 \}$ must contain a cycle, and one of the edges of this cycle, call it $e_2$, is not in $T_1$.

Since $e_2$ is a edge different from $e_1$ and is contained in exactly one of $T_1$ or $T_2$, it must be that $w ( e_1 ) < w ( e_2 )$. Note that $T = T_2 \cup \{ e_1 \} \setminus \{ e_2 \}$ is a spanning tree. The total weight of $T$ is smaller than the total weight of $T_2$, but this is a contradiction, since we have supposed that $T_2$ is a minimum spanning tree.

$\endgroup$ 8 $\begingroup$

A proof using cycle property:

Let $G=(V,E)$ be the original graph.

Suppose there are two distinct MSTs $T_1=(V,E_1)$ and $T_2=(V,E_2)$. Since $T_1$ and $T_2$ are distinct, the sets $E_1-E_2$ and $E_2-E_1$ are not empty, so $ \exists e\in E_1-E_2$.

Since $e\notin E_2$, adding it to $T_2$ creates a cycle. By cycle property the most expensive edge of this cycle (call it $e'$) does not belong to any MST. But

If $e'=e$ then $e'\in E_1$ (because $e\in E_1-E_2$)
If $e'\neq e$ then $e'\in E_2$

Both cases are contradicting with the fact that $e'$ is not in any MST.

$\endgroup$ 0 $\begingroup$

The best explanation I found was on wikipedia, 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 a MST, $\{e1\}\cup B$ must contain a cycle $C$.
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. Replacing $e2$ with $e1$ in $B$ therefore yields a spanning tree with a smaller weight.
7. This contradicts the assumption that $B$ is a MST.

More generally, if the edge weights are not all distinct then only the (multi-)set of weights in minimum spanning trees is certain to be unique; it is the same for all minimum spanning trees [1].

$\endgroup$ $\begingroup$

This is a slightly different (though more lengthy) proof than the other's in that it is an algorithmic proof. We can use Prim's algorithm and demonstrate the proof by studying the spanning tree it builds in such a graph $G$. Here is Prim's algorithm:

• $V_T \leftarrow \{ v_0 \}$
• $T_0 \leftarrow \emptyset$
• for $i \leftarrow 1$ to $|V| - 1$ do:
  • find an edge $e_i=(v_i,u_i)$ of minimum weight such that $v_i$ is in $V_T$ and $u_i$ is not.
  • $V_T \leftarrow V_T \cup \{ u_i \}$
  • $T_i \leftarrow T_i \cup \{ e_i \}$

We demonstrate the following : At iteration $i$, the choice $e_i$ that Prim's algorithm makes belongs to every minimum spanning tree. We can show this by using the inductive hypothesis:

Suppose $T_{i-1}$ is a subset of every minimum spanning tree. Then, $T_i = T_{i-1} \cup \{ e_i \}$ is a subset of every minimum spanning tree.

• Base case: $T_1 = e_1$ where $e_1$ is incident to $v_0$. Suppose that there is some minimum spanning tree $T$ that does not contain $e_1$. Then, $T$ contains another edge, $\bar{e}_1$ incident to $v_0$. By the greedy choice of Prim's and the distinctness of weights, $w(e_1) < w(\bar{e}_1)$ and we can replace $\bar{e}_1$ with $e_1$ to decrease the weight of $T$, which is a contradiction.

• Inductive step: Suppose, to the contrary, that there exists some minimum spanning tree $T$ which contains the edges in $T_{i-1}$ but does not contain $e_i$. Consider the set of edges $T \setminus T_{i-1}$, which must be a forest composed of trees $$\bar{T}^1_{i-1}, \bar{T}^2_{i-1}, \ldots, \bar{T}^k_{i-1},$$where each tree $\bar{T}^t_{i-1}$ is connected to $T_{i-1}$ in $T$ by an edge $e^t_{i-1}$.

  However, note that one of those trees must be incident to the vertex $u_i$. Suppose that tree is $\bar{T}^x_{i-1}$. Then, by Prim's greedy choice and since the weights of edges are distinct, we know that $w(e_i) < w(e^x_{i-1})$. Which means that we replace $e^x_{i-1}$ with $e_i$ and decrease the weight of $T$. Hence, $T$ is not a minimum spanning tree. Then, $e_i$ must be in every minimum spanning tree and $T_i$ must be a subset of every minimum spanning tree.

Thus, the minimum spanning tree produced by Prim's algorithm is the only minimum spanning tree of $G$.

$\endgroup$ 1 $\begingroup$

This is a (slightly) more detailed version of the currently accepted answer

(For the sake of contradiction) Let $T_1 = (V, E_1)$ and $T_2 = (V, E_2)$ be two distinct MSTs of the graph $G = (V, E)$
Note that both have the same vertex set $V$ since both are spanning trees of $G$

Consider the set $E_{\Delta} = E_1 \triangle E_2$
Let $e = (u, v)$ be the edge in $E_{\Delta}$ having the least cost (or weight)
Note that since all costs are unique, and $E_{\Delta}$ is non-empty, $e$ must be unique.
Without loss of generality, assume $e \in E_1$

Now, there must be a path $P$, with $e \notin P$, in $T_2$ connecting $u$ and $v$, since trees are by definition, connected.
Note that at least one edge (say $e'$) that occurs in $P$ must not be in $E_1$, thus, $e' \in E_{\Delta}$
This is because, if $P \subset E_1$, $T_1$ will contain a cycle formed by the path $P$ and the edge $e$, this leads to a contradiction, since trees by definition are acyclic.
Note that by definition of $e$ and the fact that all costs are distinct, $\text{cost}(e) < \text{cost}(e')$

Now, consider $T_2' = (V, E_2')$, where $E_2' = (E_2 \backslash\{e'\})\cup\{e\}$, this has a strictly lesser total cost than $T_2$
As $T_2$ was a MST, this leads to a contradiction.

$\endgroup$

Your Answer

Sign up or log in

Sign up using Google Sign up using Facebook Sign up using Email and Password Submit

Post as a guest

Post Your Answer Discard

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