Maximum Weight Edge in all Minimum Spanning Trees is Bridge

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$ that belongs to every minimum spanning tree of $G$.


Let $e$ have maximum weight in $G$.

Then $e$ is a bridge in $G$.


Proof