Edge is Minimum Weight Bridge iff in All Minimum Spanning Trees

From ProofWiki
Jump to navigation Jump to search

Theorem

Let $G$ be an undirected network.

Let every edge of $G$ have a unique weight.

Let $e$ be an edge of $G$.


Then $e$ is a bridge of minimum weight in $G$ if and only if $e$ belongs to every minimum spanning tree of $G$.


Proof

Necessary Condition

Aiming for a contradiction, suppose $e$ is a bridge of minimum weight that does not belong to some minimum spanning tree $Q$.

Let $e$ be added to $Q$ to make $Q'$.

Then $e$ forms part of a unique cycle $C$ in $Q$.

Thus there exists an edge $f \in C$ such that $w \left({Q}\right) < w \left({Q + e - f}\right)$.

This contradicts the minimality of $Q$.

$\Box$



Sufficient Condition