Minimum spanning tree contains edge of minimum weight

448 Views Asked by At

Let $G=(V,E)$ be a weighted undirected graph with weight function $w:E\rightarrow \mathbb R$ and $S,T$ a partition of $V$. Let $e$ be an edge of minimum weight among all edges with one endpoint in $S$ and one in $T$.
Show that there is a minimal spanning tree that contains $e$.
My idea:
Suppose there is no MST $F$ that contains $e$ and $e'$ be an an edge in $F$ with one endpoint in $S$ and one in $T$. Adding $e$ to $F$ will give a cycle. So if we delete $e'$ and add $e$ we will get a MST with lower weight since $w(e)<w(e')$.
How can I improve my proof?

1

There are 1 best solutions below

0
On

You have the right idea: show that any spanning tree that does not contain $e$ can be modified to yield one that does, without increasing the total weight. So let $F$ be a spanning tree that does not contain $e$. Argue that there exists an edge $e’\not=e$ with one end in $S$ and one end in $T$. Then replace $e’$ with $e$ and note that $w(e)\le w(e’)$. (You mistakenly have $<$ in your proposed proof.)