Let $G$ be a minimum spanning tree of a complete graph. Let $e$ be the maximum weight edge in $G$. I'd like to proof that given any other spanning tree $G'$ of this graph, being $j$ the maximum weight edge of $G'$, then $w(e) \leq w(j)$.

I really don't know if this is true, and I can't think of any counterexample to proof the opposite.

Any suggestions?

  • 1
    $\begingroup$ Well, that doesn't seem right. Set all edge weights to 1. Then $w(e) = 1 = w(j)$, so we can't have $w(e) < w(j)$. What I think should be true is $w(e) \leq w(j)$. $\endgroup$ – Manuel Lafond May 28 '14 at 19:05
  • $\begingroup$ Yes, makes sense, I'll edit $\endgroup$ – FranckN May 28 '14 at 19:08
  • $\begingroup$ Hint: Think of the cut property of the minimum spanning tree problem. In any cut which includes $e$, we know that $e$ must be the minimum weight edge in this cut. Any spanning tree $G'$ must contain at least one edge from this cut. Hence $w(e) \le w(j)$. And we are done. $\endgroup$ – Obinna Okechukwu May 28 '14 at 19:55

The cut property of the Minimum Spanning Tree (MST) problem is what you should look at. i.e. Any edge $\{x,y\}$ in an MST has weight at least as small as the edge with smallest weight in the cut that separates $x$ and $y$. This can easily be shown by contradiction.

In any cut which includes the edge $e$ (i.e. separates it's two adjacent vertices), we know that $e$ must be an edge with minimum weight in this cut.

Any spanning tree $G'$ must contain at least one edge in this cut.

Let $e'$ be such an edge. We know that $$w(e') \ge w(e)$$ We also know that $$w(j) \ge w(e')$$ So, $$w(j) \ge w(e') \ge w(e)$$

| cite | improve this answer | |
  • $\begingroup$ How can you assume that $w(j) \geq w(e')$ ? For instance you could have $e', j$ and $e$ all in the same cut, and I don't see what prevents $w(e') > w(j)$. In fact, the point is that if $w(j) < w(e)$ then $G'$ uses no edge in the cut of $e$, and thus $G'$ can't be a spanning tree. $\endgroup$ – Manuel Lafond May 28 '14 at 20:16
  • $\begingroup$ The cut property as described on wikipedia is quite different from what I'm referring to (maybe I should delete the link then and state it explicitly). $\endgroup$ – Obinna Okechukwu May 28 '14 at 20:19
  • $\begingroup$ But still, say that $e'$ is the (single) edge with the highest weight in the graph, and $G'$ doesn't include it. Then $w(j) < w(e')$. $\endgroup$ – Manuel Lafond May 28 '14 at 20:28
  • $\begingroup$ I don't see what you are saying. Isn't $w(j)$ the largest weight in $G'$? Note that $j \in G'$ and $e' \in G'$. $\endgroup$ – Obinna Okechukwu May 28 '14 at 20:30
  • 1
    $\begingroup$ Ah everything is fine then. My apologies ! I though $e'$ was any edge in the cut, not one included by $G'$. $\endgroup$ – Manuel Lafond May 28 '14 at 20:40

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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