2
$\begingroup$

Let $G(V,E,w)$ be a weighted graph with vertex set $V$, edge set $E$ and weights $w:E \rightarrow \mathbb{R}_+$. Suppose there is a unique edge $e \in E$ with smallest weight, that is, $w(e)< w(f)$ for all edges $f \in E$. Prove that every minimum weight spanning tree (MST) of $G$ must include $e$.

$\endgroup$
2
$\begingroup$

$\textit{Proof}.$ Suppose $|V| = n$. Let $T$ be a MST of $G$. Since $T$ is a tree and contains all vertices of $G$, $T$ contains $n-1$ edges.

Suppose, (toward a contradiction), that $T$ does not contain $e$. The augmented graph $T+e$ contains $n$ edges and $n$ vertices, and must therefore contain a cycle. At least one of the other edges (call it $f$) in that cycle must have weight strictly larger than that of $e$ (by hypotheses). Hence, drop $f$ and we now have a spanning tree of $G$ with a smaller total weight than $T$, which is a contradiction since we assumed $T$ to a be a MST. Hence, our initial assumption that $T$ does not contain $e$ must be false. The result follows.

$\endgroup$

Your Answer

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