Bridge (graph theory)

For a connected graph, a bridge can uniquely determine a cut.

bridges, since adding additional edges must create a cycle.

The bridge-block tree of the graph has a vertex for every nontrivial component and an edge for every bridge.

[3] An important open problem involving bridges is the cycle double cover conjecture, due to Seymour and Szekeres (1978 and 1979, independently), which states that every bridgeless graph admits a multi-set of simple cycles which contains each edge exactly twice.

[5] It performs the following steps: A very simple bridge-finding algorithm[6] uses chain decompositions.

Chain decompositions do not only allow to compute all bridges of a graph, they also allow to read off every cut vertex of G (and the block-cut tree of G), giving a general framework for testing 2-edge- and 2-vertex-connectivity (which extends to linear-time 3-edge- and 3-vertex-connectivity tests).

For each vertex v in ascending DFS-numbers 1...n, traverse every backedge (i.e. every edge not in the DFS tree) that is incident to v and follow the path of tree-edges back to the root of T, stopping at the first vertex that is marked as visited.