Graph Bridges
Graph Bridges
Definition: For a connected graph $G = (V(G), E(G))$, a Bridge is an edge whose removal would make $G$ become a disconnected graph. |
For example, let's look at the following graph with all bridge edges being coloured in blue:
We consider the blue edges to be bridges, as their removal would break the graph into two distinct parts. Note that if we remove only one of the black edges, then the graph is still connected.