# 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 $$ 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.