Editing Bridge (graph theory)

{{Short description|Edge in node-link graph whose removal would disconnect the graph}}
[[Image:Graph cut edges.svg|thumb|upright=0.85|A graph with 16 vertices and six bridges (highlighted in red)]]
[[Image:Undirected.svg|thumb|upright=0.6|An undirected connected graph with no bridge edges]]

In [[graph theory]], a '''bridge''', '''isthmus''', '''cut-edge''', or '''cut arc''' is an [[Glossary of graph theory#edge|edge]] of a [[Graph (discrete mathematics)|graph]] whose deletion increases the graph's number of [[Connected component (graph theory)|connected components]].<ref>{{citation
 | last = Bollobás | first = Béla | author-link = Béla Bollobás
 | doi = 10.1007/978-1-4612-0619-4
 | isbn = 0-387-98488-7
 | location = New York
 | mr = 1633290
 | page = 6
 | publisher = Springer-Verlag
 | series = Graduate Texts in Mathematics
 | title = Modern Graph Theory
 | url = https://books.google.com/books?id=SbZKSZ-1qrwC&pg=PA6
 | volume = 184
 | year = 1998}}.</ref> Equivalently, an edge is a bridge if and only if it is not contained in any [[Cycle (graph theory)|cycle]]. For a connected graph, a bridge can uniquely determine a [[Cut (graph theory)|cut]]. A graph is said to be '''bridgeless''' or '''isthmus-free''' if it contains no bridges.

This type of bridge should be distinguished from an unrelated meaning of "bridge" in graph theory, a subgraph separated from the rest of the graph by a specified subset of vertices; see [[Glossary of graph theory#bridge|bridge]] in the [[Glossary of graph theory]].

==Trees and forests==
A graph with <math>n</math> nodes can contain at most <math>n-1</math> bridges, since adding additional edges must create a cycle. The graphs with exactly <math>n-1</math> bridges are exactly the [[tree (graph theory)|trees]], and the graphs in which every edge is a bridge are exactly the [[forest (graph theory)|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.<ref>{{citation
 | last1 = Westbrook | first1 = Jeffery | author1-link = Jeff Westbrook
 | last2 = Tarjan | first2 = Robert E. | author2-link = Robert Tarjan
 | doi = 10.1007/BF01758773
 | issue = 5–6
 | journal = Algorithmica
 | mr = 1154584
 | pages = 433–464
 | title = Maintaining bridge-connected and biconnected components on-line
 | volume = 7
 | year = 1992}}.</ref>

==Relation to vertex connectivity==
Bridges are closely related to the concept of [[Articulation vertex|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 [[k-vertex-connected graph|2-vertex-connected]].

In a [[cubic graph]], every cut vertex is an endpoint of at least one bridge.

==Bridgeless graphs==
A '''bridgeless graph''' is a graph that does not have any bridges. Equivalent conditions are that each [[Connected component (graph theory)|connected component]] of the graph has an [[ear decomposition|open ear decomposition]],<ref name="robbins39">{{citation
 | last = Robbins | first = H. E. | authorlink = Herbert Robbins
 | journal = [[The American Mathematical Monthly]]
 | pages = 281–283
 | title = A theorem on graphs, with an application to a problem of traffic control
 | volume = 46
 | year = 1939
 | issue = 5 | doi=10.2307/2303897| jstor = 2303897 | hdl = 10338.dmlcz/101517
 | hdl-access = free
 }}.</ref> that each connected component is [[K-edge-connected graph|2-edge-connected]], or (by [[Robbins' theorem]]) that every connected component has a [[strong orientation]].<ref name="robbins39"/>

An important open problem involving bridges is the [[cycle double cover conjecture]], due to [[Paul Seymour (mathematician)|Seymour]] and [[George Szekeres|Szekeres]] (1978 and 1979, independently), which states that every bridgeless graph admits a multi-set of simple cycles which contains each edge exactly twice.<ref>{{citation
 | last = Jaeger | first = F.
 | contribution = A survey of the cycle double cover conjecture
 | doi = 10.1016/S0304-0208(08)72993-1
 | pages = 1–12
 | series = North-Holland Mathematics Studies
 | title = Annals of Discrete Mathematics 27 – Cycles in Graphs
 | volume = 27
 | year = 1985| isbn = 978-0-444-87803-8
 }}.</ref>

==Tarjan's bridge-finding algorithm==
The first [[linear time]] algorithm (linear in the number of edges) for finding the bridges in a graph was described by [[Robert Tarjan]] in 1974.<ref>{{citation
 | last = Tarjan | first = R. Endre | author-link = Robert Tarjan
 | doi = 10.1016/0020-0190(74)90003-9
 | year = 1974
 | issue = 6
 | journal = Information Processing Letters
 | mr = 0349483
 | pages = 160–161
 | title = A note on finding the bridges of a graph
 | volume = 2}}.</ref> It performs the following steps:
* Find a [[spanning forest]] of <math>G</math>
* Create a [[Tree_(graph_theory)#Rooted_tree|Rooted forest]] <math>F</math> from the spanning forest
* Traverse the forest <math>F</math> in [[Tree traversal#Pre-order, NLR|preorder]] and number the nodes. Parent nodes in the forest now have lower numbers than child nodes.
* For each node <math>v</math> in preorder (denoting each node using its preorder number), do:
** Compute the number of forest descendants <math>ND(v)</math> for this node, by adding one to the sum of its children's descendants.
** Compute <math>L(v)</math>, the lowest preorder label reachable from <math>v</math> by a path for which all but the last edge stays within the subtree rooted at <math>v</math>. This is the minimum of the set consisting of the preorder label of <math>v</math>, of the values of <math>L(w)</math> at child nodes of <math>v</math> and of the preorder labels of nodes reachable from <math>v</math> by edges that do not belong to <math>F</math>.
** Similarly, compute <math>H(v)</math>, the highest preorder label reachable by a path for which all but the last edge stays within the subtree rooted at <math>v</math>. This is the maximum of the set consisting of the preorder label of <math>v</math>, of the values of <math>H(w)</math> at child nodes of <math>v</math> and of the preorder labels of nodes reachable from <math>v</math> by edges that do not belong to <math>F</math>.
** For each node <math>w</math> with parent node <math>v</math>, if <math>L(w) = w</math> and <math>H(w) <  w + ND(w)</math> then the edge from <math>v</math> to <math>w</math> is a bridge.

==Bridge-finding with chain decompositions==
A very simple bridge-finding algorithm<ref name="Schmidt">{{citation
 | last = Schmidt | first = Jens M. | author-link = Jens M. Schmidt
 | doi = 10.1016/j.ipl.2013.01.016
 | issue = 7
 | journal = Information Processing Letters
 | pages = 241–244
 | year = 2013
 | title = A Simple Test on 2-Vertex- and 2-Edge-Connectivity
 | volume = 113| arxiv = 1209.0700}}.</ref> uses [[chain decomposition]]s.
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 [[Biconnected component|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).

Chain decompositions are special ear decompositions depending on a DFS-tree ''T'' of ''G'' and can be computed very simply: Let every vertex be marked as unvisited. For each vertex ''v'' in ascending [[Depth-first search|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. During such a traversal, every traversed vertex is marked as visited. Thus, a traversal stops at the latest at ''v'' and forms either a directed path or cycle, beginning with v; we call this path
or cycle a ''chain''. The ''i''th chain found by this procedure is referred to as ''C<sub>i</sub>''. ''C=C<sub>1</sub>,C<sub>2</sub>,...'' is then a ''[[chain decomposition]]'' of ''G''.

The following characterizations then allow to ''read off'' several properties of ''G'' from ''C'' efficiently, including all bridges of ''G''.<ref name="Schmidt"/> Let ''C'' be a chain decomposition of a simple connected graph ''G=(V,E)''.
# ''G'' is 2-edge-connected if and only if the chains in ''C'' partition ''E''.
# An edge ''e'' in ''G'' is a bridge if and only if ''e'' is not contained in any chain in ''C''.
# If ''G'' is 2-edge-connected, ''C'' is an [[ear decomposition]].
# ''G'' is 2-vertex-connected if and only if ''G'' has minimum degree 2 and ''C<sub>1</sub>'' is the only cycle in ''C''.
# A vertex ''v'' in a 2-edge-connected graph ''G'' is a cut vertex if and only if ''v'' is the first vertex of a cycle in ''C - C<sub>1</sub>''.
# If ''G'' is 2-vertex-connected, ''C'' is an [[Ear decomposition|open ear decomposition]].

== Bridges and Eulerian cycles ==
Define an '''[[Eulerian graph]]''' as a graph with an Eulerian cycle. Every Eulerian graph is bridgeless. This is because in an Eulerian graph every edge is a part of an Eulerian cycle. Hence, if the edge is deleted, then its endpoints remain connected through the rest of the cycle. But the opposite is not true.

Define an '''almost Eulerian graph''' as a graph that can be made Eulerian by adding a single edge (equivalently, a graph that contains an Eulerian trail). Every almost-Eulerian graph is almost-bridgeless, but the opposite is not true.

The classes of bridgeless graphs and almost-Eulerian graphs have a non-empty intersection (the Eulerian graphs are both bridgeless and almost-Eulerian), but they do not contain each other.<ref>{{Cite journal |last=Bei |first=Xiaohui |last2=Elkind |first2=Edith |last3=Segal-Halevi |first3=Erel |last4=Suksompong |first4=Warut |date=2025-03-31 |title=Dividing a Graphical Cake |url=https://epubs.siam.org/doi/full/10.1137/22M1500502 |journal=SIAM Journal on Discrete Mathematics |volume=39 |issue=1 |pages=19–54 |doi=10.1137/22M1500502 |issn=0895-4801}}</ref>{{Rp|location=Appendix.B}}

==See also==
* [[Biconnected component]]
* [[Cut (graph theory)]]

==Notes==
{{Reflist}}

{{Authority control}}

[[Category:Graph connectivity]]