graph theoryoptimizationtrees
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?
The claim is false.
Consider a graph $G$ with points $a,b,c,d,e$ and edges $(a,b),(b,c),(c,d),(d,e),(e,a),(a,d)$ where all edges have weight 1, except $(a,b)$ and $(a,e)$ which have weight 100. Then there is only one minimum spanning tree, namely $(b,c),(c,d),(d,e),(a,e)$.
If instead the claim was the following: "If a graph $G$ is a cycle, and two of the edges $e_1$ and $e_2$ have weight $w$ which is the maximum weight in $G$, then there are at least two different minimum spanning trees in $G$"
Then the claim is true. Consider some spanning tree $T$ in $G$. Since $T$ is spanning, one of the edges, lets say $e_1$ with weight $w$ must be in $T$. Now consider a new tree $T' = T - e_1 + e_2$. Now one can easily show that $T'$ is also spanning and has the same weight as $T$.
Part $(b)$ is only true if we assume that $G$ has multiple edges but no loops.
The Wikipedia page is a little misleading; it might be more accurate to say that at least one of the lowest weight edges will be in a minimum spanning tree (in a loopless graph).
This is apparent from the application of Kruskal's Algorithm for constructing a minimum spanning tree. Essentially, select the lowest weight vertex at each step that will not introduce a cycle. Because it is impossible to create a cycle when selecting the first edge in a loopless graph (per assumption) Kruskal's Algorithm will always select it.
In order to rule out the length $10$,$10$, $11$, and $13$ edges, they must all create cycles if they are included with the $8$ edge; this implies that there is a multiple edge with $8$,$10$,$10$,$11$, and $13$ all connecting the same two vertices.
I would say it's very non-standard to allow multiple-edges but not loops in the graph, because problems are generally a matter of simple vs. non-simple, where loops are allowed in non-simple graphs. Clearly, you can obtain a higher result by making $8$,$10$,$10$, and $11$ edges all loops, while using the other $4$ to create the spanning tree.
I would ask your professor to clarify this point, and definitely ask during an exam if a question is vague.
Best Answer
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.