Definition:Bridge (Graph Theory)

From ProofWiki
Jump to navigation Jump to search

Definition

Let $G = \struct {V, E}$ be a connected graph.

Let $e \in E$ be an edge of $G$ such that the edge deletion $G - e$ is disconnected.


Then $e$ is known as a bridge of $G$.


Example

In the graph below, $CD$ is a bridge.


Bridge.png


The graph would be separated into the two components $ABC$ and $DEF$.


Sources