0
$\begingroup$

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

$\endgroup$
2
  • $\begingroup$ Well you can assume it is a minimum spanning tree and get a contradiction, but at the moment it is just a spanning tree $\endgroup$
    – Gabi G
    Commented Dec 5, 2018 at 17:20
  • $\begingroup$ This is the classic fact that a minimum spanning tree is a bottleneck spanning tree. $\endgroup$
    – John L.
    Commented Dec 6, 2018 at 0:35

1 Answer 1

2
$\begingroup$

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.