Proving that a spanning tree of graph is not a minimum Let $G$ be an undirected and connected graph. Let $T$ be a spanning tree of $G$ with edges weights: $w_1 \le, w_2 \le ... \le w_{n-1}$ which are responing to the edges. $e_1,e_2,...,e_{n-1}$.

Now I assume that there exists a spanning tree of $G$, let's call it $T'$, that has a path from node $u$ to node $v$ with all edges in a path from weight $&lt;w_i$ for some $1 \le i \le n-1$. And I assume that the path from $u$ to $v$ in $T$ has at least one edge with weight $\ge w_i$. I other words, the path from $u$ to $v$ in $T$ has an edge which is heavier than all the edges in the corresponding path in $T'$.

I need to prove formally that $T$ is not a MST.

What I've tried is to somehow find a tree which is of less wight than $T$ using Kruskal's algorithm, but I couldn't manage to do it.
If you remove that edge you mentioned with weight $\geq w_i$ from $T$, then the new $T$ has two components (because it's a tree). But one of the edges on the cheap path connecting $u$ and $v$ in $T'$ would reconnect these two components in $T$. And the substitution saved you a bit in terms of weight.