Relation Between Bridges And Spanning Trees
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$.