# Proof involving maximum weight of edge in minimum spanning tree

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?

• 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)$. – Manuel Lafond May 28 '14 at 19:05
• Yes, makes sense, I'll edit – FranckN May 28 '14 at 19:08
• 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. – 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)$$

• 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. – Manuel Lafond May 28 '14 at 20:16
• 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). – Obinna Okechukwu May 28 '14 at 20:19
• 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')$. – Manuel Lafond May 28 '14 at 20:28
• 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'$. – Obinna Okechukwu May 28 '14 at 20:30
• Ah everything is fine then. My apologies ! I though $e'$ was any edge in the cut, not one included by $G'$. – Manuel Lafond May 28 '14 at 20:40