Given a graph with distinct edge weights and a not-minimum ST, there always exist another ST of lesser total weight that differs only by one edge I have to show that, if all the edge weights of a graph are distinct, given a spanning tree $T$ that is not a MST, there always exist a spanning tree $T'$ of lesser total weight, s.t. $T'$ differs from $T$ only by one edge.
I started reasoning from this question, but it's not helpful for my case and I cannot go over.
 A: Actually that question (in particular this answer) is helpful.
A proof using cycle property:
Let $G=(V,E)$ be the original graph. Let the set of edges $T \subseteq E$ be a spanning tree on $G$ that is not minimum.
Now, there will exist an edge $e$ which belongs to the MST and not to $T$.
Adding $e$ it to $T$ creates a cycle. By cycle property, the most expensive edge of this cycle (call it $e'$) does not belong to the MST, so it must belong to $T$.
Removing $e'$ we break the cycle and we obtain a new subgraph $T'$ with lesser total weight than $T$. Furthermore, $T'$ is a spanning tree because:


*

*It doesn't have cycles: we broke the cycle removing $e'$.

*It is connected: creating and breaking a cycle cannot affect connectivity.

*It covers all the vertices of $G$: the two vertices of the removed edge $e'$ are still covered by the adjacent edges of $e'$.


So there must exist a spanning tree of lesser total weight, s.t. it differs from $T$ only by one edge.
A: Consider a spanning tree $E$ and label its edges $e_1$, $\ldots$,$e_n$. Consider now a spanning tree $F$. Then there exists a labeling of the edges of $F$ $\  $ $f_1$, $\ldots$, $f_n$ so that the following are still spanning trees (use an exchange lemma like for two bases of a vector space):
$$(e_1, e_2, \ldots, e_{n-1},e_n) \\
  (e_1, e_2, \ldots, e_{n-1},f_n)\\
  (e_1, e_2, \ldots, f_{n-1}, f_n)\\
   \ldots \\
  (e_1, f_2, \ldots, f_{n-1}, f_n)\\
  (f_1, f_2, \ldots, f_{n-1}, f_n)$$
Assume now that $E$ is obtained using the greedy algorithm: 
$e_1$ is of minimal weight, $e_2$ is of minimal weight so that $e_1$, $e_2$ form no cycles, $e_3$ is of minimal weight so that 
$e_1$, $e_2$, $e_3$ form no cycles, and so on, up to $e_n$. From the above we conclude that $w(e_i) \le w(f_i)$ for all $i$. 
Since $F$ is arbitrary we conclude that $E$ is a minimal tree. 
Now assume that $F$ itself is not a minimal  tree. Then for some $i$ we have a strict inequality $w(e_i) < w(f_i)$.
 Let $i$ the smallest index for which this happens. Let's assume now that all the edges have different weights. Then 
we have $e_1= f_1$, $\ldots$,$e_{i-1} =f_{i-1}$. Hence the tree $(e_1, \ldots, e_{i-1}, f_{i}, \ldots, f_n)$ is $F$ and
the tree $(e_1, \ldots, e_{i-1}, e_i, f_{i+1}, \ldots, f_n)$ is obtained from it by exchanging the edge $e_i$ with an edge of 
larger weight $f_i$. 
A: This is true even if not all the edge weights are distinct. 
Define 
$$ w'(e) = \begin{cases} 2 \cdot w(e) &\text{ if } e \text{ belongs to } T \\ 2 \cdot w(e) + 1 & \text{otherwise}\end{cases} $$
then sort all the edges according to $w'$ (rather than $w$). Observe that it produces the same ordering as sorting according to $w$ only that it prioritizes edges of $T$ if possible. Now run the Kruskal's algorithm using that new ordering and denote by $e$ the first edge not in $T$ that was chosen by the algorithm.
Let $e'$ be the heaviest edge on the cycle created by $e$ in $T \cup \{e\}$. Observe that $e$ does not create a cycle with edges of strictly smaller $w'$, otherwise it would not be chosen by the algorithm. Thus $w'(e) \leq w'(e')$, and so $w(e) < w'(e')$, because $e$ is not in $T$ while $e'$ is. Therefore we can set $T' = T \setminus \{e'\} \cup \{e\}$.
I hope this helps $\ddot\smile$
