Relation Between Bridges And Spanning Trees

From ProofWiki
Jump to navigation Jump to search

Theorem

Edge is Bridge iff in All Spanning Trees

Let $G$ be a simple graph.

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


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


Edge is Minimum Weight Bridge iff in All Minimum Spanning Trees

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$.


Maximum Weight Edge in all Minimum Spanning Trees is Bridge

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$.