Bridge (graph theory)

In graph theory, a bridge, isthmus, cut-edge, or cut arc is an edge of a graph whose deletion increases its number of connected components. Equivalently, an edge is a bridge if and only if it is not contained in any cycle. A graph is said to be bridgeless or isthmus-free if it contains no bridges. In graph theory, a bridge, isthmus, cut-edge, or cut arc is an edge of a graph whose deletion increases its number of connected components. Equivalently, an edge is a bridge if and only if it is not contained in any cycle. A graph is said to be bridgeless or isthmus-free if it contains no bridges. Another meaning of 'bridge' appears in the term bridge of a subgraph. If H is a subgraph of G, a bridge of H in G is a maximal subgraph of G that is not contained in H and is not separated by H. A graph with n {displaystyle n} nodes can contain at most n − 1 {displaystyle n-1} bridges, since adding additional edges must create a cycle. The graphs with exactly n − 1 {displaystyle n-1} bridges are exactly the trees, and the graphs in which every edge is a bridge are exactly the forests. In every undirected graph, there is an equivalence relation on the vertices according to which two vertices are related to each other whenever there are two edge-disjoint paths connecting them. (Every vertex is related to itself via two length-zero paths, which are identical but nevertheless edge-disjoint.) The equivalence classes of this relation are called 2-edge-connected components, and the bridges of the graph are exactly the edges whose endpoints belong to different components. The bridge-block tree of the graph has a vertex for every nontrivial component and an edge for every bridge. Bridges are closely related to the concept of articulation vertices, vertices that belong to every path between some pair of other vertices. The two endpoints of a bridge are articulation vertices unless they have a degree of 1, although it may also be possible for a non-bridge edge to have two articulation vertices as endpoints. Analogously to bridgeless graphs being 2-edge-connected, graphs without articulation vertices are 2-vertex-connected. In a cubic graph, every cut vertex is an endpoint of at least one bridge. A bridgeless graph is a graph that does not have any bridges. Equivalent conditions are that each connected component of the graph has an open ear decomposition, that each connected component is 2-edge-connected, or (by Robbins' theorem) that every connected component has a strong orientation. 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 set of simple cycles which contains each edge exactly twice. The first linear time algorithm for finding the bridges in a graph was described by Robert Tarjan in 1974. It performs the following steps: