Graph Bridges
Table of Contents

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.

Unless otherwise stated, the content of this page is licensed under Creative Commons Attribution-ShareAlike 3.0 License