Why does no minimal spanning tree contain the longest edge of a circuit?

Question

Let $G=(V,E)$ be a graph with lengthfunction $l:E\rightarrow\mathbb{R}$. How do I prove that if $e$ is a line in a circuit $C$ such that $l(e)>l(f)$ for all $f\in C$ with $f\neq e$, then we get that no minimal spanning tree for $G$ contains $e$?

Answer 1

The key here is that if you have a spanning tree $T$ of a connected graph $G$, and $f$ is an edge not in $T$, then $T\cup f$ has a unique cycle. Moreover, if $e$ is an edge in this cycle, $(T\cup f)\setminus e$ is also a spanning tree of $G$.

Now let $T$ be a spanning tree of $G$ and suppose it contains your longest edge $e$. Then there must be an edge $f$ in $C$ that is not in $T$ (as otherwise $T$ would contain $C$, which it can't since $T$ is a tree). Then $(T\cup f)\setminus e$ is a spanning tree of $G$ with less total length than $T$ since $l(f)<l(e)$.